- 难度:
简单
- 本题涉及算法:
迭代
二叉树
- 思路:
迭代
二叉树
- 类似题型:
题目 面试题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, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
方法一 迭代
解题思路
- 祖先的定义: 若节点
p
在节点root
的左(右)子树中,或p = root
,则称root
是p
的祖先。
最近公共祖先的定义: 设节点 root
为节点 p, q
的某公共祖先,若其左子节点 root.left
和右子节点 root.right
都不是 p,q 的公共祖先,则称 root
是 “最近的公共祖先” 。
根据以上定义,若 root
是 p, q
的 最近公共祖先 ,则只可能为以下情况之一:
p
和q
在 root 的子树中,且分列root
的 异侧(即分别在左、右子树中);p = root
,且q
在root
的左或右子树中;q = root
,且p
在root
的左或右子树中;
本题给定了两个重要条件:① 树为 二叉搜索树 ,② 树的所有节点的值都是 唯一 的。根据以上条件,可方便地判断 p,q
与 root
的子树关系,即:
- 若
root.val < p.val
,则p
在root
右子树 中; - 若
root.val > p.val
,则p
在root
左子树 中; - 若
root.val = p.val
,则p
和root
指向 同一节点 。
方法一:迭代
- 循环搜索: 当节点
root
为空时跳出;- 当
p, q
都在root
的 右子树 中,则遍历至root.right
; - 否则,当
p, q
都在root
的 左子树 中,则遍历至root.left
; - 否则,说明找到了 最近公共祖先 ,跳出。
- 当
- 返回值: 最近公共祖先
root
。
代码
java
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(root != null) {
if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
root = root.right; // 遍历至右子节点
else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
root = root.left; // 遍历至左子节点
else break;
}
return root;
}
}
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val > q.val: p,q = q,p # 保证 p.val < q.val
while root:
if root.val < p.val:
root = root.right # 右子数
elif root.val > q.val:
root = root.left # 左子数
else:
break
return root
方法二 递归
# 递归
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if not root: return
if root.val < p.val and root.val < q.val:
root = self.lowestCommonAncestor(root.right,p,q)
if root.val > q.val and root.val > p.val:
root = self.lowestCommonAncestor(root.left,p,q)
return root
PREVIOUS1. 两数之和
NEXT面试题64. 求1+2+…+n