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

简介: 当给定一个二叉搜索树时, 如何找到该树中两个指定节点的最近公共祖先?本文带大家解决这个问题。

一、leetcode算法



1、二叉搜索树的最近公共祖先


1.1、题目


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


百度百科中最近公共祖先的定义为:“对于有根树 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、思路


思路一:本题注意到题目中给出的是一棵「二叉搜索树」,因此我们可以快速地找出树中的某个节点以及从根节点到该节点的路径,例如我们需要找到节点 pp:


我们从根节点开始遍历;


如果当前节点就是 pp,那么成功地找到了节点;


如果当前节点的值大于 pp 的值,说明 pp 应该在当前节点的左子树,因此将当前节点移动到它的左子节点;


如果当前节点的值小于 pp 的值,说明 pp 应该在当前节点的右子树,因此将当前节点移动到它的右子节点。


1.3、答案


18.png


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


相关文章
|
1月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
2月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
35 2
|
2月前
【LeetCode 45】701.二叉搜索树中的插入操作
【LeetCode 45】701.二叉搜索树中的插入操作
14 1
|
2月前
【LeetCode 44】235.二叉搜索树的最近公共祖先
【LeetCode 44】235.二叉搜索树的最近公共祖先
20 1
|
2月前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
43 0
|
2月前
【LeetCode 47】669.修剪二叉搜索树
【LeetCode 47】669.修剪二叉搜索树
13 0
|
2月前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
21 0
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
22 0
|
2月前
【LeetCode 42】501.二叉搜索树中的众数
【LeetCode 42】501.二叉搜索树中的众数
10 0
|
2月前
【LeetCode 41】530.二叉搜索树的最小绝对差
【LeetCode 41】530.二叉搜索树的最小绝对差
15 0