二叉树的最近公共祖先

LeetCode –236（二叉树的最近公共祖先）

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

解法一

通过存储每个节点对应的父节点，来寻找最近公共祖先

• 首先通过map存储节点对应的父节点
• 寻找其中一个节点p的所有的父节点，存储在list中
• 遍历q节点的父节点是否在list中，如果在list中表示找到，直接返回。否则没找到返回null。

代码为：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    HashMap<TreeNode,TreeNode> map = new HashMap<>();  //存储节点所对应的直接父节点
    List<TreeNode> list = new ArrayList<>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ceature(root);
        while (p!=null){
            list.add(p); //将p所涉及到的父节点存储到list中
            p = map.get(p);
        }
        while (q!=null){
            if (list.contains(q)) return q;  //判断是否在p的父节点中，如果在则直接是最近的祖先节点，如果不在，则在判断该节点的父节点
            q = map.get(q);
        }
        return null;
    }
    //将节点所对应的父节点存储到map中
    public void ceature(TreeNode root){
        if (root.left!=null){
            map.put(root.left,root);
            ceature(root.left);
        }
        if (root.right!=null){
            map.put(root.right,root);
            ceature(root.right);
        }
    }
}

解法二

递归，分别判断p和q节点是否在根节点的两侧还是左侧还是右侧。

• 在左侧查找节点p和节点q，判断是否存在。
• 如果都存在左侧或右侧，则在左侧或右侧查找
• 否则直接返回根节点

代码为：

/**
 * 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) return null;
        if (p.val==root.val || q.val==root.val) return root;
        //如果p和q在左子树中
        if (find(root.left,p) && find(root.left,q)) return lowestCommonAncestor(root.left,p,q);
        //如果p和q在右子树中
        if (find(root.right,p) && find(root.right,q)) return lowestCommonAncestor(root.right,p,q);
        //如果p和q在根节点两侧，
        return root;
    }
    //判断node是否在root中
    public boolean find(TreeNode root,TreeNode node){
        if (root==null) return false;
        if (root.val==node.val) return true;
        return find(root.left,node) || find(root.right,node);
    }
}