236.Lowest Common Ancestor of Binary Tree(M)

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

1.Description(Medium)

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:

  4
 / \
3   7
   / \
  5   6

LCA(3, 5) =4

LCA(5, 6) =7

LCA(6, 7) =7

2.Code

https://www.jiuzhang.com/solution/lowest-common-ancestor-of-a-binary-tree/

//Lowest Common Ancestor(Binary Tree)

//在root为根的二叉树中找A,B的LCA:

// 如果找到了就返回这个LCA

// 如果只碰到A，就返回A

// 如果只碰到B，就返回B

// 如果都没有，就返回null

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {

        if(root==null || root==A || root==B){//当前节点为空或者是AB其中一个就返回当前节点
            return root;
        }

        //Divided
        TreeNode left=lowestCommonAncestor(root.left,A,B);
        TreeNode right=lowestCommonAncestor(root.right,A,B);

        //Conquer
        if(left!=null && right!=null){  //AB位于左右子树两侧
            return root;
        }
        if(left!=null){            //此处右子树应该为空，因为找不到A,B任何一个，AB全在左子树上
            return left;
        }
        if(right!=null){
            return right;
        }

        return null;       

    }

这个LCA延伸有个BST的LCA：

Given the root of a binary search tree and two values, find the least common ancestor of the two

values.

Solution：

This is a relatively straightforward recursive solution once we realize that the lowest common ancestor

is the first node where each of the two values we are looking for lies in different child subtrees of the

node we are looking for. We simply search recursively down as we would searching for a value in a

binary search tree until our paths diverge. At that point, we return the node at which our paths diverge.

都大往左走，都小往右走。

Time :O(n) Space:O(1)

public Node findLowestCommonAncestor(Node node, int value1, int value2) {
 if (node == null)
    return null;

 if (node.value > value2 && node.value > value1)
    return findLowestCommonAncestor(node.left, value1, value2);
 else if (node.value < value2 && node.value < value1)
    return findLowestCommonAncestor(node.right, value1, value2);
 else
    return node;
 }

Solution: https://mp.weixin.qq.com/s/9RKzBcr3I592spAsuMH45g

遇到任何递归型的问题，无非就是灵魂三问：

1、这个函数是干嘛的？

2、这个函数参数中的变量是什么的是什么？

3、得到函数的递归结果，你应该干什么？

呵呵，看到这灵魂三问，你有没有感觉到熟悉？本号的动态规划系列文章，篇篇都在说的动态规划套路，首先要明确的是什么？是不是要明确「定义」「状态」「选择」，这仨不就是上面的灵魂三问吗？

下面我们就来看看如何回答这灵魂三问。

首先看第一个问题，这个函数是干嘛的？或者说，你给我描述一下lowestCommonAncestor这个函数的「定义」吧。

描述：给该函数输入三个参数root，p，q，它会返回一个节点。

情况 1，如果p和q都在以root为根的树中，函数返回的即使p和q的最近公共祖先节点。

情况 2，那如果p和q都不在以root为根的树中怎么办呢？函数理所当然地返回null呗。

情况 3，那如果p和q只有一个存在于root为根的树中呢？函数就会返回那个节点。

题目说了输入的p和q一定存在于以root为根的树中，但是递归过程中，以上三种情况都有可能发生，所以说这里要定义清楚，后续这些定义都会在代码中体现。

OK，第一个问题就解决了，把这个定义记在脑子里，无论发生什么，都不要怀疑这个定义的正确性，这是我们写递归函数的基本素养。

然后来看第二个问题，这个函数的参数中，变量是什么？或者说，你描述一个这个函数的「状态」吧。

描述：函数参数中的变量是root，因为根据框架，lowestCommonAncestor(root)会递归调用root.left和root.right；至于p和q，我们要求它俩的公共祖先，它俩肯定不会变化的。

第二个问题也解决了，你也可以理解这是「状态转移」，每次递归在做什么？不就是在把「以root为根」转移成「以root的子节点为根」，不断缩小问题规模嘛？

最后来看第三个问题，得到函数的递归结果，你该干嘛？或者说，得到递归调用的结果后，你做什么「选择」？

这就像动态规划系列问题，怎么做选择，需要观察问题的性质，找规律。那么我们就得分析这个「最近公共祖先节点」有什么特点呢？刚才说了函数中的变量是root参数，所以这里都要围绕root节点的情况来展开讨论。

先想 base case，如果root为空，肯定得返回null。如果root本身就是p或者q，比如说root就是p节点吧，如果q存在于以root为根的树中，显然root就是最近公共祖先；即使q不存在于以root为根的树中，按照情况 3 的定义，也应该返回root节点。

以上两种情况的 base case 就可以把框架代码填充一点了：

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) 
{    
    // 两种情况的 base case    
    if (root == null) return null;    
    if (root == p || root == q) return root;    
    TreeNode left = lowestCommonAncestor(root.left, p, q);    
    TreeNode right = lowestCommonAncestor(root.right, p, q);
}

现在就要面临真正的挑战了，用递归调用的结果left和right来搞点事情。根据刚才第一个问题中对函数的定义，我们继续分情况讨论：

情况 1，如果p和q都在以root为根的树中，那么left和right一定分别是p和q（从 base case 看出来的）。

情况 2，如果p和q都不在以root为根的树中，直接返回null。

情况 3，如果p和q只有一个存在于root为根的树中，函数返回该节点。

明白了上面三点，可以直接看解法代码了：

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) 
{    
    // base case    
    if (root == null) return null;    
    if (root == p || root == q) return root;    
    TreeNode left = lowestCommonAncestor(root.left, p, q);    
    TreeNode right = lowestCommonAncestor(root.right, p, q);    
    // 情况 1    
    if (left != null && right != null) {        return root;    }    
    // 情况 2    
    if (left == null && right == null) {        return null;    }    
    // 情况 3    
    return left == null ? right : left;
}

对于情况 1，你肯定有疑问，left和right非空，分别是p和q，可以说明root是它们的公共祖先，但能确定root就是「最近」公共祖先吗？

这就是一个巧妙的地方了，因为这里是二叉树的后序遍历啊！前序遍历可以理解为是从上往下，而后序遍历是从下往上，就好比从p和q出发往上走，第一次相交的节点就是这个root，你说这是不是最近公共祖先呢？

综上，二叉树的最近公共祖先就计算出来了。