LeetCode Lowest Common Ancestor of a Binary Tree Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

---

给定一棵二叉树和两个节点p,q，问p和q的最近公共祖先节点是哪个。LCA问题。 思路：要找p和q的最近公共祖先，很直观的方法是找到从根节点分别到p和q的路径，然后把其中一条路径（比如根到p）上的点hash成path1，从另一条路径（比如根到q）的底端（q）往根节点走，把走过的每个点去path1中找，如果找到，则就是他们的LCA，因为这是距离q最近、且在path1中的点。 但是怎样找到根到p和q的路径呢。这里换一种思路，定义如下新的数据结构，par表示该节点的父节点，根节点的父节点为-1。 [cpp] struct MyNode { TreeNode* node; int par; MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {}; }; [/cpp] 先整体把树层次遍历一遍，成为一个保存MyNode的数组，记录每个点的父节点在数组中的下标。在遍历的同时，记录下p和q节点的下标。这样通过下标往前递归就可以找到p和q到根节点的路径了。 找到路径之后，对其中一条路径hash，另一条路径在该hash中找。代码如下： [cpp] class Solution { private: struct MyNode { TreeNode* node; int par; MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {}; }; public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { vector<MyNode> nodes; int i = 0, j = 0; queue<MyNode> tree; tree.push({ root,-1 }); while (!tree.empty()) { MyNode cur = tree.front(); tree.pop(); if (cur.node == NULL) continue; if (cur.node == p)i = nodes.size(); if (cur.node == q)j = nodes.size(); tree.push({ cur.node->left,nodes.size() }); tree.push({ cur.node->right,nodes.size() }); nodes.push_back(cur); } if (i == j)return nodes[i].node; unordered_set<int> path1; while (i != -1) { path1.insert(i); i = nodes[i].par; } while (j != -1) { if (path1.find(j) != path1.end()) { return nodes[j].node; } j = nodes[j].par; } return NULL; } }; [/cpp] 本代码提交AC，用时19MS。 讨论区还有一种递归的解法，很有意思。我们在以root为根的树中找p和q的LCA，如果root等于p或q其中之一，说明p或q就是他们的LCA。否则分别在左子树和右子树中递归的找LCA，如果发现在左右子树中找到的LCA都不为null，说明他们p和q分别位于root的两个子树，类似样例中的5和1，则root就是他们的LCA。如果某个子树返回的LCA为空，说明p和q都不在这个子树中，则先遇到谁，谁就是LCA，比如样例中的5和4，都不在3的右子树，在递归3的左子树的时候，先遇到了5，所以5是LCA。 完整代码如下： [cpp] class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL || root == p || root == q)return root; TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left != NULL&&right != NULL)return root; return left != NULL ? left : right; } }; [/cpp] 本代码提交AC，用时23MS。]]>