#235. Lowest Common Ancestor of a Binary Search Tree

題目描述

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

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

限制條件

樹的節點總數在[2,10^5]之間。
-10^9 <= 節點值 <= 10^9
所有節點值都是唯一的。
p != q
p 和 q 都會存在於樹上。
祖先節點同時也可以是後代節點。

解題思路

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

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

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

遞迴 Recursion & 深度優先搜尋(BSF)

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)open in new window。
遞迴與深度優先搜尋(BSF)的應用。