236. (LCA) Lowest Common Ancestor of a Binary Tree

time: O(n)

space:O(n)

/*
    236. Lowest Common Ancestor of a Binary Tree

    1. 終止條件
    2. 找左子樹
    3. 找右子樹
    4. 如果在左右子樹找到pq, 代表pq一個在左一個在右, root就會是LCS
    5. 如果只有在某一邊找到, 代表pq在同一側, 所以LCS就是某一邊找到的本身結果（題目中有提到LCS可以是p或q本身）

    time complexity: O(n), space complexity: O(n)

 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p.equals(root) || q.equals(root) {
            return root; // 1.terminal condition, find p,q or not find pq => null
        }
        
        TreeNode left = lowestCommonAncestor(root.left, p, q); //2.find left side for p, q
        TreeNode right = lowestCommonAncestor(root.right, p, q); //3.find right side for p, q

        if (left != null && right != null) {
            return root; // 4.if find p,q in left and right side, root is LCS !
        }
        return left != null ? left : right; // 5.if only one side find p or q (it means p,q are all in one side), it's the answer because in question we allow a node to be a descendant of itself
    }
}

另一個思路, 用 count, 其實一樣啦...

class Solution {
    TreeNode res = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return res;
    }
    private int dfs(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left, p, q);
        int right = dfs(node.right, p, q);
        int self = (node.val == p.val || node.val == q.val) ? 1 : 0;
        int count = left + right + self;
        if (count == 2 && res == null) {
            res = node;
        }
        return count;
    }
}