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 thedefinition 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 allowa node to be a descendant of itself).”

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

For example, the lowest common ancestor (LCA) of nodes5and1is3. Another example is LCA of nodes5and4is5, since a node can be a descendant of itself according to the LCA definition.

思路分析

这道题刚拿到之后感觉应该是用post order traverse来做，因为要对比左右子树是不是包含node p或者node q，但是刚开始没有弄清楚如何返回结果。

宏观分析递归实现：

思想：bottom-up

定义：递归函数的定义是当前(sub)tree中的LCA node

退出条件：当遇到了null，node p，或者node q就往上pass it to its parent

function：找到root节点的左子树的lowestCommonAncestor右子树的lowestCommonAncestor，然后如果左子树的lowestCommonAncestor跟右子树的lowestCommonAncestor都不是null，那就说明p，q节点位于root的两边，返回root，如果一个是null，说明以root为根节点的subtree中之包含p，q中的一个节点，那么就返回不是null的lowestCommonAncestor。

具体实现：

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;
    }
}

微观分析：_post order遍历节点，如果某个节点的左右子树分别包括这两个节点，那么这个节点必然是所求的解，返回该节点。否则，返回左或者右子树（哪个包含p或者q的就返回哪个）

f(root.left, p, q)  ---                                
                       |            
                       |——>f(root, p, q)
                       |                
f(root.right, p, q) ---