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.
Return null if LCA does not exist.

Example

For the following binary tree:

  4
 / \
3   7
   / \
  5   6
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7

思路

比如例题中找3，5的LCA

Picture1.png

1. 遍历树，找遍历的节点是否为target。
2. 如果当前root 为空，则返回null。
3. 如果当前root为target，则返回该root。
4. 如果当前root，其left child为空，只有right child不为空那么返回right child。反之亦然
5. 如果当前root，left child 和 right child都不为空，则说明找到了LCA，返回当前root

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        
        TreeNode result = helper(root, p, q);
        return result;
    }
    
    private TreeNode helper(TreeNode root, TreeNode p, TreeNode q) {
        // stop条件: 如果root为空，则返回null
        if (root == null) {
            return null;
        }
        
        TreeNode leftNode = helper(root.left, p, q);
        TreeNode rightNode = helper(root.right, p, q);
        
        // 1. 找到当前root是一个target，就返回这个root
        if (root == p || root == q) {
            return root;
        }
        
        //2. 当前root下的分支其中包含了某个target，就把这个target 返回出去。
        if (leftNode != null && rightNode == null) {
            return leftNode;
        }
        
        if (rightNode != null && leftNode == null) {
            return rightNode;
        }
        
        //3. 如果root的左、右child分支都已经找到了target，那么说明当前的root就是最小公共节点了，直接返回当前root
        if (leftNode != null && rightNode != null) {
            return root;
        }
        return null;
    }
}

Solution2： 第二部分是BST的代码，根据BST全部右大于root，全部左小于root的特性。根据p 和q的值来缩小检索范围

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // bottom - up
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        /*************** BINARY TREE Solution：无法根据左右值大小缩小检索范围 *******************/
        // If either p or q matches with root's key, report 
        // the presence by returning root (Note that if a key is 
        // ancestor of other, then the ancestor key becomes LCA
        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        
        TreeNode left = lowestCommonAncestor (root.left, p, q);
        TreeNode right = lowestCommonAncestor (root.right, p, q);
        
        // If both of the above calls return Non-NULL, then one key 
        // is present in once subtree and other is present in other, 
        // So this node is the LCA 
        if (left != null && right != null) {
            return root;
        }
        
        // Otherwise check if left subtree or right subtree is LCA 
        // 例如p q分别是2，4. 找到6的左子树2找到了，直接返回node2。并没有再向下找了。
        // 但是右子树 8 这边就没有找到返回null。
        // 但因为题目给出的条件就是 一定能在BST中找到P and Q。所以此种情况表明2就肯定是LCA
        return left != null ? left : right;
        /*************** BINARY TREE Solution：END*******************/
        ///////
        ///////
        ///////
        
        /*************** BST Solution *******************/
        // 1. 如果p, q都在node的左边（不包含），那么就搜左子树
        // 2. 如果p, q都在node的右边（不包含），那么就搜右子树
        // 3。如果p，q在node两侧，或者node 等于 p或者q，那么就找到了直接返回当前node
        
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor (root.left, p, q);
        }
        
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor (root.right, p, q);
        }
        
        return root;
        /*************** BST Solution END*******************/
    }
    
}