Code More Create

Appearance

Return to top
On this page

68-I.二叉搜索树的最近公共祖先

题目描述

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

输出: 6

解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

输出: 2

解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

思路分析

思路1

可以先存储两个结点的路径，再进行比对

思路2

可以直接遍历树，起点为根节点，当两个结点的值都小于某个结点的值，那么肯定都在该结点的左树，那么结果可能就是左节点，保存下来，再接着前进，直到两个结点不在同一边时，此时最后保存下来的结点就是结果

AC 代码

解法一 

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pPath = getPath(root,p);
        List<TreeNode> qPath = getPath(root,q);
        TreeNode ans = root;
        for(int i = 0; i < pPath.size() && i < qPath.size(); i++){
            if(pPath.get(i).val == qPath.get(i).val){
                ans = pPath.get(i);
            }else{
                break;
            }
        }
        return ans;
    }
    public List<TreeNode> getPath(TreeNode root,TreeNode node){
        List<TreeNode> path = new ArrayList<>();
        path.add(root);
        while(root.val != node.val){
            if(root.val > node.val){
                root = root.left;
            }else if(root.val < node.val){
                root = root.right;
            }else{
                break;
            }
            path.add(root);
        }
        return path;
    }
}

解法二 

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		// 起点是根节点
        TreeNode ans = root;
        while(true){
            if(ans.val > p.val && ans.val > q.val){
				// 如果p、q值都小于公共结点的值，将公共结点更新为左节点
                ans = ans.left;
            }else if(ans.val < p.val && ans.val < q.val){
				// 如果p、q值都大于公共结点的值，将公共结点更新为右节点
                ans = ans.right;
            }else{
				// 当两个点不在同一边时，循环结束
                break;
            }
        }
        return ans;
    }
}

总结

如果你还有更多的思考、分析、总结，通通都加上来吧~