leetcode

0 class Solution {

1 public:

2 int diameterOfBinaryTree(TreeNode *root) {

3 unordered_map<TreeNode *, int> um;

4 stack<TreeNode *> st;

5 int res = 0;

6

7 while (root) {

8 st.push(root);

9 root = root->left;

10 }

11

12 while (!st.empty()) {

13 TreeNode *root = st.top();

14 st.pop();

15 if (um.find(root) == um.end()) {

16 um.insert({root, 1});

17 st.push(root);

18 root = root->right;

19 while (root) {

20 st.push(root);

21 root = root->left;

22 }

23 } else {

24 if (!root->left && !root->right) continue;

25 int l = um[root->left];

26 int r = um[root->right];

27 res = max(l + r, res);

28 um[root] = 1 + max(l, r);

29 }

30 }

31

32 return res;

33 }

34 };