Lowest Common Ancestor

Question

Problem Statement

Given the root and two nodes in a Binary Tree. Find the lowest common
ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the
ancestor of both nodes.

Example

For the following binary tree:

  1.   4
  2.  / \
  3. 3   7
  4.    / \
  5.   5   6

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

题解1 - 自底向上

初次接触这种题可能会没有什么思路，在没有思路的情况下我们就从简单例子开始分析！首先看看3和5，这两个节点分居根节点4的两侧，如果可以从子节点往父节点递推，那么他们将在根节点4处第一次重合；再来看看5和6，这两个都在根节点4的右侧，沿着父节点往上递推，他们将在节点7处第一次重合；最后来看看6和7，此时由于7是6的父节点，故7即为所求。从这三个基本例子我们可以总结出两种思路——自顶向下(从前往后递推)和自底向上(从后往前递推)。

顺着上述实例的分析，我们首先看看自底向上的思路，自底向上的实现用一句话来总结就是——如果遍历到的当前节点是 A/B 中的任意一个，那么我们就向父节点汇报此节点，否则递归到节点为空时返回空值。具体来说会有如下几种情况：

  1. 当前节点不是两个节点中的任意一个，此时应判断左右子树的返回结果。
    • 若左右子树均返回非空节点，那么当前节点一定是所求的根节点，将当前节点逐层向前汇报。// 两个节点分居树的两侧
    • 若左右子树仅有一个子树返回非空节点，则将此非空节点向父节点汇报。// 节点仅存在于树的一侧
    • 若左右子树均返回NULL, 则向父节点返回NULL. // 节点不在这棵树中
  2. 当前节点即为两个节点中的一个，此时向父节点返回当前节点。

根据此递归模型容易看出应该使用先序/后序遍历来实现。

C++ Recursion From Bottom to Top

  1. /**
  2.  * Definition of TreeNode:
  3.  * class TreeNode {
  4.  * public:
  5.  *     int val;
  6.  *     TreeNode *left, *right;
  7.  *     TreeNode(int val) {
  8.  *         this->val = val;
  9.  *         this->left = this->right = NULL;
  10.  *     }
  11.  * }
  12.  */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param root: The root of the binary search tree.
  17.      * @param A and B: two nodes in a Binary.
  18.      * @return: Return the least common ancestor(LCA) of the two nodes.
  19.      */
  20.     TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
  21.         // return either A or B or NULL
  22.         if (NULL == root || root == A || root == B) return root;
  24.         TreeNode *left = lowestCommonAncestor(root->left, A, B);
  25.         TreeNode *right = lowestCommonAncestor(root->right, A, B);
  27.         // A and B are on both sides
  28.         if ((NULL != left) && (NULL != right)) return root;
  30.         // either left or right or NULL
  31.         return (NULL != left) ? left : right;
  32.     }
  33. };

Java

  1. /**
  2.  * Definition of TreeNode:
  3.  * public class TreeNode {
  4.  *     public int val;
  5.  *     public TreeNode left, right;
  6.  *     public TreeNode(int val) {
  7.  *         this.val = val;
  8.  *         this.left = this.right = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.     /**
  14.      * @param root: The root of the binary search tree.
  15.      * @param A and B: two nodes in a Binary.
  16.      * @return: Return the least common ancestor(LCA) of the two nodes.
  17.      */
  18.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
  19.         if (root == null) return null;
  21.         TreeNode lNode = lowestCommonAncestor(root.left, A, B);
  22.         TreeNode rNode = lowestCommonAncestor(root.right, A, B);
  23.         // root is the LCA of A and B
  24.         if (lNode != null && rNode != null) return root;
  25.         // root node is A/B(including the case below)
  26.         if (root == A || root == B) return root;
  27.         // return lNode/rNode if root is not LCA
  28.         return (lNode != null) ? lNode : rNode;
  29.     }
  30. }

源码分析

结合例子和递归的整体思想去理解代码，在root == A || root == B后即层层上浮(自底向上)，直至找到最终的最小公共祖先节点。

最后一行return (NULL != left) ? left : right;将非空的左右子树节点和空值都包含在内了，十分精炼！[^leetcode]

fixme 细心的你也许会发现，其实题解的分析漏掉了一种情况，即树中可能只含有 A/B 中的一个节点！这种情况应该返回空值，但上述实现均返回非空节点。

关于重复节点：由于这里比较的是元素地址，因此可以认为树中不存在重复元素，否则不符合树的数据结构。

题解 - 自底向上(计数器)

为了解决上述方法可能导致误判的情况，我们可以对返回结果添加计数器来解决。由于此计数器的值只能由子树向上递推，故应该用后序遍历。在类中添加私有变量较为方便, C++中的写法较为复杂，后续再优化。

定义pair<TreeNode *, int> result(node, counter)表示遍历到某节点时的返回结果，返回的node表示LCA 路径中的可能的最小节点，相应的计数器counter则表示目前和A或者B匹配的节点数，若计数器为2，则表示已匹配过两次，该节点即为所求，若只匹配过一次，还需进一步向上递推。表述地可能比较模糊，还是看看代码吧。

C++

  1. /**
  2.  * Definition of TreeNode:
  3.  * class TreeNode {
  4.  * public:
  5.  *     int val;
  6.  *     TreeNode *left, *right;
  7.  *     TreeNode(int val) {
  8.  *         this->val = val;
  9.  *         this->left = this->right = NULL;
  10.  *     }
  11.  * }
  12.  */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param root: The root of the binary search tree.
  17.      * @param A and B: two nodes in a Binary.
  18.      * @return: Return the least common ancestor(LCA) of the two nodes.
  19.      */
  20.     TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
  21.         if ((NULL == A) || (NULL == B)) return NULL;
  23.         pair<TreeNode *, int> result = helper(root, A, B);
  25.         if (A != B) {
  26.             return (2 == result.second) ? result.first : NULL;
  27.         } else {
  28.             return (1 == result.second) ? result.first : NULL;
  29.         }
  30.     }
  32. private:
  33.     pair<TreeNode *, int> helper(TreeNode *root, TreeNode *A, TreeNode *B) {
  34.         TreeNode * node = NULL;
  35.         if (NULL == root) return make_pair(node, 0);
  37.         pair<TreeNode *, int> left = helper(root->left, A, B);
  38.         pair<TreeNode *, int> right = helper(root->right, A, B);
  40.         // return either A or B
  41.         int count = max(left.second, right.second);
  42.         if (A == root || B == root)  return make_pair(root, ++count);
  44.         // A and B are on both sides
  45.         if (NULL != left.first && NULL != right.first) return make_pair(root, 2);
  47.         // return either left or right or NULL
  48.         return (NULL != left.first) ? left : right;
  49.     }
  50. };

Java

  1. /**
  2.  * Definition of TreeNode:
  3.  * public class TreeNode {
  4.  *     public int val;
  5.  *     public TreeNode left, right;
  6.  *     public TreeNode(int val) {
  7.  *         this.val = val;
  8.  *         this.left = this.right = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.     private int count = 0;
  14.     /**
  15.      * @param root: The root of the binary search tree.
  16.      * @param A and B: two nodes in a Binary.
  17.      * @return: Return the least common ancestor(LCA) of the two nodes.
  18.      */
  19.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
  20.         TreeNode result = helper(root, A, B);
  21.         if (A == B) {
  22.             return result;
  23.         } else {
  24.             return (count == 2) ? result : null;
  25.         }
  26.     }
  28.     private TreeNode helper(TreeNode root, TreeNode A, TreeNode B) {
  29.         if (root == null) return null;
  31.         TreeNode lNode = helper(root.left, A, B);
  32.         TreeNode rNode = helper(root.right, A, B);
  33.         // root is the LCA of A and B
  34.         if (lNode != null && rNode != null) return root;
  35.         // root node is A/B(including the case below)
  36.         if (root == A || root == B) {
  37.             count++;
  38.             return root;
  39.         }
  40.         // return lNode/rNode if root is not LCA
  41.         return (lNode != null) ? lNode : rNode;
  42.     }
  43. }

源码分析

在A == B时，计数器返回1的节点即为我们需要的节点，否则只取返回2的节点，如此便保证了该方法的正确性。对这种实现还有问题的在下面评论吧。

Reference