返回

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

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

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

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

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

示例 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 为不同节点且均存在于给定的二叉搜索树中

思路

利用回溯从底向上搜索,遇到一个节点的左子树里有p,右子树里有q,那么当前节点就是最近公共祖先。

那么本题是二叉搜索树,二叉搜索树是有序的,那得好好利用一下这个特点

因为是有序树,那么只要从上到下去遍历,遇到 cur节点是数值在[p, q]区间中则一定可以说明该节点cur就是q 和 p的公共祖先

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    for {
        if root.Val > p.Val && root.Val > q.Val {
            // root大于p q 向左搜索
            root = root.Left // 更新root
        }
        if root.Val < p.Val && root.Val < q.Val {
            // root小于p q 向右搜索
            root = root.Right
        }
        if (root.Val-p.Val)*(root.Val-q.Val) <= 0 {
            // root在p q之间,找到最近公共祖先就是root
            return root
        }
    }
    return root
}

GitHub

Built with Hugo
Theme Stack designed by Jimmy