235. 二叉搜索树的最近公共祖先

题目:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

代码:

class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode res = root;
        while (true){
            if (p.val < res.val && q.val < res.val) {
                //p和q都小于res,证明p和q都在res的左子树
                res = res.left;
            } else if (p.val > res.val && q.val > res.val) {
                //p和q都大于res,证明p和q都在res的右子树
                res = res.right;
            }else{
                //上述条件都不满足,证明出现分叉,跳出循环
                break;
            }
        }
        return res;
    }

}

思路:

一开始我的想法是,遍历二叉树,分别找到p和q节点并记录寻找过程中的路径pPath和qPath,并从头开始遍历两个路径,当开始出现路径不一致的值时,上一个值就是最近公共祖先。代码如下:

class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pPath = this.findPath(root, p);
        List<TreeNode> qPath = this.findPath(root, q);
        int size = Math.min(pPath.size(), qPath.size());

        TreeNode res = root;
        for (int i = 1; i < size; i++) {
            if (pPath.get(i).val == qPath.get(i).val) {
                res = pPath.get(i);
            }else{
                break;
            }
        }
        return res;
    }

    /**
     * 获取从根节点到node节点的寻找路径
     * @param root
     * @param node
     * @return
     */
    private List<TreeNode> findPath(TreeNode root, TreeNode node) {
        List<TreeNode> path = new ArrayList<>();
        TreeNode temp = root;
        path.add(root);
        while (temp.val != node.val) {
            if (node.val > temp.val) {
                //往右子树找
                temp = temp.right;
            } else {
                //往左子树找
                temp = temp.left;
            }
            path.add(temp);
        }
        return path;
    }

}

这个方法可以解决问题,但是存在多次遍历,且因为记录了路径值,所以效率不高而且内存占用还大。

在上述寻找路径的代码中,考虑到提供的是一个二叉搜索树,所以使用了二叉搜索树的特性来优化搜索效率。

二叉搜索树的特性:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。

于是乎我想到,可以使用一次遍历即可解决问题。因为对于p和q的最近公共祖先节点r来说,p和q一定分散在r的两边,即出现分叉。那么我们根据这个条件一次遍历即可找到结果。具体参考开头的代码。

支付宝搜索:344355 领取随机红包

如果文章对您有帮助,欢迎给作者打赏