236. Lowest-Common-Ancestor-of-a-Binary-Tree

difficulty: Medium

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output:
 3
Explanation: 
The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output:
 5
Explanation: 
The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Note:

• All of the nodes' values will be unique.

• p and q are different and both values will exist in the binary tree.

Method One

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 观察发现, 最近的公共祖先有什么特征呢？
    // 当 p 和 q 在自己的左右子树各一个的时候，它是一个公共祖先。
    // 还有一种情况就是，它自己是 p 和 q 之一。而且它的左右子树有一个包含另一个。
    private TreeNode ancestor;
    private TreeNode p;
    private TreeNode q;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.ancestor = root;
        this.p = p;
        this.q = q;
        dfs(root);
        return ancestor;
    }
    
    public boolean dfs(TreeNode node) {
        if(node == null) {
            return false;
        }
        
        boolean isAtLeft = dfs(node.left);
        boolean isAtRight = dfs(node.right);
        
        if( (isAtLeft || isAtRight) && (node == this.p || node == this.q ) ) {
            this.ancestor = node;
            return true;
        }
        
        if( isAtLeft && isAtRight) {
            this.ancestor = node;
            return true;           
        }
        
        if( isAtLeft || isAtRight || node == this.p || node == this.q ) {
            return true;
        }
        return false;
    }
}
​

class Solution {
    // 这个解法特别好。
    // 我们在左边找，找不到的话说明在右边。
    // 我么在右边找，找不到的话说明在左边。
    // 实际上我们做的是什么？我们做的是 postOrder 搜索，找的 target 是 p 或者 q.
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q ) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if( left == null ) {
            return right;
        }
        if( right == null ) {
            return left;
        }
        return root;
    }
}

再想一个 iterative 的写法。 第一步，用 map 记录父节点。第二步，从某个节点出发找根，然后把一路上的节点都加到set1里。 第三步，从另一个节点出发找根，如果遇到set1存在某个节点，这个就是最低的公共祖先 lca 了。

1676 这个题不错的

class Solution {
    private Set<TreeNode> nodeSet;
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        this.nodeSet = new HashSet<>();
        this.lca = null;
        for(TreeNode node : nodes){
            nodeSet.add(node);
        }
        numberOfNodesFound(root);
        return lca;
    }
    private int numberOfNodesFound(TreeNode node){
        if(node == null) return 0;
        int foundLeft = numberOfNodesFound(node.left);
        int foundRight = numberOfNodesFound(node.right);
        int totalFound = foundLeft + foundRight;
        if(nodeSet.contains(node)){
            totalFound++;
        }
        if(lca == null && totalFound == nodeSet.size()){
            lca = node;
        }
        return totalFound;
    }
}