236. Lowest Common Ancestor of a Binary Tree - Medium

前往題目

之前寫的文章

想法

• 用DFS然後每個node回傳之前要判斷並帶值
• 沒有想出關鍵的判斷部分該怎麼寫

思路

1. DFS
2. 當找到目標的a或b的時候就+1
3. 這樣搜尋到底然後準備往回的時候就會經過各個可能的ancestor，只要發現該node包含ab就可以直接回傳了

Code

class Solution {
    TreeNode res;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        res = null;
        find(root, p, q);
        return res;
    }

    private int find(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null) return 0;

        int left = find(node.left, p, q);
        int right = find(node.right, p, q);

        // Self could be ancestor as well
        int self = 0;
        if (node == p || node == q) ++self;
        // Add the count from left right and self nodes
        int count = left + right + self;
        // When found the LCA
        if (count == 2 && res == null) res = node;
        return count;
    }
}