題⽬描述

給定⼀個⼆叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先。

1. 對於該題的最近的公共祖先定義:對於有根樹T的兩個結點p 、q ，最近公共祖先LCA(T,p,q)表示⼀個結點x ，滿⾜x 是p 和q 的祖先且x 的深度儘可能⼤。在這⾥，⼀個節點也可以是它⾃⼰的祖先.
2. ⼆叉搜索樹是若它的左⼦樹不空，則左⼦樹上所有結點的值均⼩於它的根結點的值； 若它的右⼦樹不空，則右⼦樹上所有結點的值均⼤於它的根結點的值
3. 所有節點的值都是唯⼀的。
4. p 、q 為不同節點且均存在於給定的⼆叉搜索樹中。

如果給定以下搜索⼆叉樹: {7,1,12,0,4,11,14,#,#,3,5} ，如下圖:

示例1
輸⼊: {7,1,12,0,4,11,14,#,#,3,5},1,12
輸出: 7
説明：節點1 和 節點12的最近公共祖先是7

示例2：
輸⼊: {7,1,12,0,4,11,14,#,#,3,5},12,11
輸出: 12
説明：因為⼀個節點也可以是它⾃⼰的祖先.所以輸出12

思路及解答

迭代遍歷

二叉搜索樹（BST）的特性，通過迭代查找公共祖先，根據節點值大小關係，決定向左子樹或右子樹查找

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        
        TreeNode current = root;
        
        while (current != null) {
            // 如果p和q的值都小於當前節點，LCA在左子樹
            if (p.val < current.val && q.val < current.val) {
                current = current.left;
            } 
            // 如果p和q的值都大於當前節點，LCA在右子樹
            else if (p.val > current.val && q.val > current.val) {
                current = current.right;
            } 
            // 否則當前節點就是LCA
            else {
                return current;
            }
        }
        
        return null; // 未找到
    }
}

• 時間複雜度：O(h)，h為樹高，平均O(log n)，最壞O(n)
• 空間複雜度：O(1)，只使用常數空間

遞歸遍歷

遞歸判斷節點值關係，決定向左或右遞歸查找

題⽬已經保證了，兩個節點 p , q 都在樹上，我們取出根節點 7 ，假設⼩於 7 ，則在左⼦樹，如果⼤於7 ，則在右⼦樹。

需要查找的兩個節點，但凡有⼀個等於根節點，它們的⽗節點就是根節點，因為⼀個節點的⽗節點可以是⾃身（題⽬有説明）。

如果⼀個⼤於根節點，⼀個⼩於更節點，其最近公共祖先也是根節點。如果兩個都⼤於，或者兩個都⼩於，怎麼辦？

當然是遞歸，如果兩個都⼩於，那麼就取當前的左⼦樹進⾏遞歸，直到符合要求。⽐如查找，3 和 5，由於 3 和 5 都⼩於 7，那麼取左⼦樹 1 下⾯的進⾏遞歸：

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution68 {
    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        TreeNode result = commonAncestor(root, p, q);
        return result == null ? -1 : result.val;
    }
    public TreeNode commonAncestor(TreeNode root, int p, int q) {
        // 等於空
        if (root == null) {
            return null;
        }
        if (root.val == p || root.val == q) {
            // 有⼀個值等於根節點
            return root;
        }
        // 在左⼦樹
        if (p < root.val && q < root.val) {
            return commonAncestor(root.left, p, q);
        } else if (p > root.val && q > root.val) {
            // 兩個都在右⼦樹
            return commonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }
}

• 時間複雜度：O(h)，遞歸深度為樹高
• 空間複雜度：O(h)，遞歸調用棧空間

通用二叉樹

假設這道題條件改⼀下，如果不是⼆叉搜索樹，怎麼辦？

如果不是⼆叉搜索樹，那麼我們不能直接判斷出它在左⼦樹，還是在右⼦樹。不如暴⼒點，先在左⼦樹中找，如果右⼦樹沒找到，説明都在左⼦樹，如果左⼦樹沒找到，説明都在右⼦樹，如果兩個都分別存在，説明當前節點就是他們的⽗節點。

public class Solution68 {
    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        TreeNode result = commonAncestor(root, p, q);
        return result == null ? -1 : result.val;
    }
    public TreeNode commonAncestor(TreeNode root, int p, int q) {
        if (null == root) {
            return null;
        }
        if (root.val == p || root.val == q) {
            return root;
        }
        TreeNode left = commonAncestor(root.left, p, q);
        TreeNode right = commonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return root;
        }
    }
}

• 時間複雜度：O(n)，需要遍歷整個樹
• 空間複雜度：O(h)，遞歸棧深度