#236. Lowest Common Ancestor of a Binary Tree

題目描述

給你一個二元樹(BST)，請找到兩個指定節點的最近公共祖先(LCA)節點。

根據維基百科，最近公共祖先是指兩個節點p和q之間在樹T之中最低的祖先節點，p和q也可以說是該祖先節點的後代節點，同時祖先節點也可以是子孫節點。

限制條件

1. The number of nodes in the tree is in the range [2, 105].
2. -109 <= Node.val <= 109
3. 每個節點值都是唯一的。
4. p != q
5. 指定的節點p和q都存在於樹中。

解題思路

這一題的解決方式與#235 Lowest Common Ancestor of a Binary Search Tree一樣。

二元樹與二元搜尋樹

與#235不同的是，這一題的樹是一般的二元樹，與二元搜尋樹不同的是，二元樹可能會存在重複的值。 但是這一題的限制條件已經規定了節點值都是唯一的，因此不用作特別的應對。

Solution

祖先節點要成立，會有兩種狀況：

1. 左邊的所有後代節點中和右邊的所有後代節點中，要同時擁有指定的節點。
2. 祖先節點同時為指定的後代節點，以及左或右的後代節點中存在指定節點。

以上兩個條件成立，該節點就會是最近公共祖先。

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        TreeNode left = LowestCommonAncestor(root.left,p,q);
        TreeNode right = LowestCommonAncestor(root.right,p,q);
        if(left!=null && right!=null) return root;
        if(root.val==p.val || root.val==q.val) return root;
        if(left!=null) return left;
        if(right!=null) return right;        
        return null;
    }
}

複雜度分析：

• 時間複雜度：最差的情況下要檢查完整棵樹才能找到答案，時間複雜度為O(n)。
• 空間複雜度：最差的情況下要檢查完整棵樹才會結束函式，空間複雜度為O(n)。

學習重點

• 專有名詞最近公共祖先(LCA)。
• 遞迴與深度優先搜尋(BSF)的應用。