Leetcode 236. Lowest Common Ancestor of a Binary Tree（详细解析）

Leetcode 236. Lowest Common Ancestor of a Binary Tree

题目链接： Lowest Common Ancestor of a Binary Tree

难度：Medium

题目大意：

给出二叉树，找二叉树中两个节点的最近公共父亲节点。

思路：

思路1

参考 高赞回答, 利用递归思想。

思路2

参考 高赞回答,用map来存储所有节点的父亲节点，用set来存储p的所有父亲节点，然后一层一层地往上找q的父亲节点，如果这个节点也是p的父亲节点，则返回。

代码

思路1代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    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&&right!=null){
            return root;
        }
        else if(left==null){
            return right;
        }
        else{
            return left;
        }
    }
}
           

思路2代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode,TreeNode> map=new HashMap<>();//存储二叉树节点的父亲节点
        map.put(root,null);
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!map.containsKey(p)||!map.containsKey(q)){
            TreeNode node=queue.poll();
            if(node.left!=null){
                map.put(node.left,node);
                queue.offer(node.left);
            }
            if(node.right!=null){
                map.put(node.right,node);
                queue.offer(node.right);
            }
        }
        Set<TreeNode> ancestors=new HashSet<>();//存储p的所有父亲节点
        while(map.get(p)!=null){//如果p不是根节点
            ancestors.add(p);
            p=map.get(p);
        }
        ancestors.add(root);
        while(!ancestors.contains(q)){
            q=map.get(q);
        }
        return q;
    }
}