【LeetCode】Day6-二叉树的最近公共祖先

236. 二叉树的最近公共祖先【中等】

树的问题通常用递归解决

若root是p、q的最近公共祖先，则只可能是这三种情况之一：

p 和 q 在 root 的子树中，且分列 root的 异侧（即分别在左、右子树中）p=root ，且 q 在 root 的左或右子树中q=root ，且 p 在 root 的左或右子树中

p.s. 自己也是自己的祖先

因此问题转化成 ( f l e f t & & f r i g h t ) ∣ ∣ ( ( x = = p ∣ ∣ x = = q ) & & ( f l e f t ∣ ∣ f r i g h t ) ) (f_{left}&&f_{right}) || ((x==p||x==q)&&(f_{left}||f_{right})) (fleft​&&fright​)∣∣((x==p∣∣x==q)&&(fleft​∣∣fright​))

 
看了半天官方题解，感觉晕晕乎乎，直到看到了最高赞题解，讲的非常清楚，还有ppt演示

考虑通过递归对二叉树进行先序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p, q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root 。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //终止条件（自己也是自己的祖先，即找到p或q可返回root）
        if(root==p||root==q||root==null)
            return root;
        //没有找到p、q，继续找
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        //左子树无p、q，返回右子树
        if(left==null) return right;
        //右子树无p、q，返回左子树
        if(right==null) return left;
        //左右子树都找到p和q了，那就说明p和q分别在左右两个子树上，所以此时的最近公共祖先就是root
        return root;
    }
}

时间复杂度和空间复杂度均为 O ( n ) O(n) O(n)

感觉比递归法好理解多了…

dfs，用哈希表存储父结点遍历p的父结点，并记录在visited遍历q的父结点，若在visited中，则返回；否则返回空

注意记一下java里HashMap（put,get,containsKey）和HashSet（add,get,contains）的用法，区分一下，别记混

class Solution {
    MaphashMap=new HashMap();
    Setvisited=new HashSet();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //遍历存父结点哈希表
        dfs(root);
        //找p的父结点,并加入visited
        while(p!=null){
            visited.add(p.val);
            p=hashMap.get(p.val);
        }
        //找p,q最近公共祖先
        while(q!=null){
            //既是p祖先，也是q祖先，返回
            if(visited.contains(q.val)){
                return q;
            }
            q=hashMap.get(q.val);
        }
        return null;
    }
    public void dfs(TreeNode root){
        if(root.left!=null){
            hashMap.put(root.left.val,root);
            dfs(root.left);
        }
        if(root.right!=null){
            hashMap.put(root.right.val,root);
            dfs(root.right);
        }
    }
}