面試題50. 樹中兩個結點的最低公共祖先結點

題目描述：

給出一個二叉樹，找到兩個結點的最低公共祖先。比如下面的二叉樹中，5和1的最低公共祖先就是3；

4和6的最低公共祖先就是5。

\
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \      

思路：

• 如果p在左子樹裡，q在右子樹裡（或者反過來，p在右子樹，q在左子樹），說明目前節點為pq的最小祖先。
• 反之，說明pq要麼都在左子樹裡，要麼都在右子樹裡。需要分别周遊左子樹和右子樹。
• 用後續周遊的思想，從下往上，如果遇到了p（或q），就把p（或q）的值向上傳回。以下圖為例，p=3，q=9。現在要查找3和9的最近祖先。把3和9一層一層向上傳回，直到6。此時6的左子樹接收傳回值3，右子樹接收傳回值9，說明6是3和9的最近祖先。

/**
 * 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 || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q); // 從root.left找p、q
        TreeNode right = lowestCommonAncestor(root.right, p, q); // 從root.right找p、q

        //if(left != null && right != null) return root;

        // 替換成下面的語句也可以
        if((left == p && right == q)||(left == q && right == p)) {
            return root;
        }
        return (left != null) ? left : right;
    }
}