My C++ solution using dfs


  • 8
    Z

    To get the LCA(Lowest Common Ancestor) of TreeNode p and q, the algorithm works as following:

    1. Use dfs to calculate the depth and parent for each TreeNode;

    2. Suppose depth[p] > depth[q], then let d = depth[p]-depth[q], first move p upwards d times and then move both p and q upwards until p and q point to the same node, which is the LCA of p and q;

      class Solution {
      public:
      TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
      unordered_map<TreeNode*, int> depth;
      unordered_map<TreeNode*, TreeNode*> parent;
      dfs(root, NULL, 0, depth, parent);
      if (depth[p] < depth[q])
      swap(p, q);
      int d = depth[p]-depth[q];
      for (int i=0; i<d; i++)
      p = parent[p];
      while (p != q) {
      q = parent[q];
      p = parent[p];
      }
      return p;
      }
      void dfs(TreeNode* node, TreeNode* p, int d,
      unordered_map<TreeNode*, int>& depth,
      unordered_map<TreeNode*, TreeNode*>& parent) {
      if (!node) return;
      depth[node] = d;
      parent[node] = p;
      dfs(node->left, node, d+1, depth, parent);
      dfs(node->right, node, d+1, depth, parent);
      }
      };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.