• 欢迎光临~

leetcode 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最近公共祖先(简单)

开发技术 开发技术 2022-10-04 次浏览

一、题目大意

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

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

例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

leetcode 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最近公共祖先(简单)

示例 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, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。

  • p、q 为不同节点且均存在于给定的二叉搜索树中。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、解题思路

求二叉树的最小共同父节点,可以用递归来求解,同志二叉搜索树的特点是左<根<右,所以根节点的值一直都是中间值,大于左子树的所有节点值,小于右子树的所有节点值,我们可以做如下判断,如果根节点的值大于p和q之间的较大值,说明q和q都在左子树中,那么此时我们就进入根节点的左子节点继续uxjv,如果根节点小于p和q之间的较小值,说明p和q都在右子树中,那么此时我们就进入根节点的右子节点继续递归,如果都不是,则说明当前根节点就是是耳濡目染共同父节点,直接返回即可。

三、解题方法

3.1 Java实现

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        if (root.val > Math.max(p.val, q.val)) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < Math.min(p.val, q.val)) {
            return lowestCommonAncestor(root.right, q, q);
        } else {
            return root;
        }
    }
}

四、总结小记

  • 2202/10/4 假期疫情瞬息万变
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com