leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0543.cpp (921B)

      1 class Solution {
      2   public:
      3     int diameterOfBinaryTree(TreeNode *root) {
      4         unordered_map<TreeNode *, int> um;
      5         stack<TreeNode *> st;
      6         int res = 0;
      7 
      8         while (root) {
      9             st.push(root);
     10             root = root->left;
     11         }
     12 
     13         while (!st.empty()) {
     14             TreeNode *root = st.top();
     15             st.pop();
     16             if (um.find(root) == um.end()) {
     17                 um.insert({root, 1});
     18                 st.push(root);
     19                 root = root->right;
     20                 while (root) {
     21                     st.push(root);
     22                     root = root->left;
     23                 }
     24             } else {
     25                 if (!root->left && !root->right) continue;
     26                 int l = um[root->left];
     27                 int r = um[root->right];
     28                 res = max(l + r, res);
     29                 um[root] = 1 + max(l, r);
     30             }
     31         }
     32 
     33         return res;
     34     }
     35 };