LeetCode题目总结-二叉搜索树

我们发现:

  • 在链表中,插入、删除速度很快O(1),但查找速度较慢O(n)
  • 在数组中,查找速度很快O(1),但插入、删除速度很慢O(n)

为了解决这个问题,我们需要寻找一种能够在插入、删除、查找、遍历等操作都相对快的容器,于是人们发明了二叉搜索树(二叉树仅作为二叉搜索树的基础)。二叉搜索树的插入、删除、查找成本均为O(log n)

二叉搜索树的性质

  • 如果节点的左子树不空,则左子树上所有结点的值均小于等于它的根结点的值;
  • 如果节点的右子树不空,则右子树上所有结点的值均大于等于它的根结点的值;
  • 任意节点的左、右子树也分别为二叉搜索树;

二叉搜索树的查找、插入、删除过程

查找

通过二叉搜索树查找节点,理想情况下我们需要检查的节点数可以减半。

但是二叉搜索树十分依赖于树中节点的拓扑结构,也就是节点间的布局关系。下图描绘了一个节点插入顺序为 20, 50, 90, 150, 175, 200 的二叉搜索树。这些节点是按照递升顺序被插入的,结果就是这棵树没有广度(Breadth)可言。也就是说,它的拓扑结构其实就是将节点排布在一条线上,而不是以扇形结构散开,所以查找时间也为 O(n)

下面是一个查找过程:

插入

当向树中插入一个新的节点时,该节点将总是作为叶子节点。所以,最困难的地方就是如何找到该节点的父节点。

下面是一个插入过程:

删除

删除节点算法的第一步是定位要被删除的节点,这可以使用前面介绍的查找算法,因此运行时间为 O(logn)。接着应该选择合适的节点来代替删除节点的位置,它共有三种情况需要考虑。

  • 情况 1:如果被删除的节点没有右孩子,那么就选择它的左孩子来代替原来的节点。二叉搜索树的性质保证了被删除节点的左子树必然符合二叉搜索树的性质。因此左子树的值要么都大于,要么都小于被删除节点的父节点的值,这取决于被删除节点是左孩子还是右孩子。因此用被删除节点的左子树来替代被删除节点,是完全符合二叉搜索树的性质的。
  • 情况 2:如果被删除节点的右孩子没有左孩子,那么这个右孩子被用来替换被删除节点。因为被删除节点的右孩子都大于被删除节点左子树的所有节点,同时也大于或小于被删除节点的父节点,这同样取决于被删除节点是左孩子还是右孩子。因此,用右孩子来替换被删除节点,符合二叉搜索树的性质。
  • 情况 3:如果被删除节点的右孩子有左孩子,就需要用被删除节点右孩子的左子树中的最下面的节点来替换它,就是说,我们用被删除节点的右子树中最小值的节点来替换

LeetCode相关题目

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

题目描述

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

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

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

示例 1:

1
2
3
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

1
2
3
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

思路

最近公共子节点有可能是下面这几种情况:

具体步骤如下:

  • 从根节点开始遍历树
  • 如果节点 p 和节点 q 都在右子树上,那么以右孩子为根节点继续 1 的操作
  • 如果节点 p 和节点 q 都在左子树上,那么以左孩子为根节点继续 1 的操作
  • 如果条件 2 和条件 3 都不成立,这就意味着我们已经找到节 p 和节点 q 的 LCA 了

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

Python实现

方法1:递归

1
2
3
4
5
6
7
8
9
10
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right,p,q)

elif root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left,p,q)

else:
return root

方法2:迭代

1
2
3
4
5
6
7
8
9
10
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
cur_node = root
while cur_node:
if p.val > cur_node.val and q.val > cur_node.val:
cur_node = cur_node.right
elif p.val < cur_node.val and q.val < cur_node.val:
cur_node = cur_node.left
else:
return cur_node

450-删除二叉搜索树中的节点

题目描述

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

  1. 首先找到需要删除的节点;
  2. 如果找到了,删除它。

说明: 要求算法时间复杂度为 O(h),h 为树的高度。

示例:

1
2
3
4
5
6
7
8
root = [5,3,6,2,4,null,7]
key = 3

5
/ \
3 6
/ \ \
2 4 7

给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

1
2
3
4
5
    5
/ \
4 6
/ \
2 7

另一个正确答案是 [5,2,6,null,4,null,7]

1
2
3
4
5
  5
/ \
2 6
\ \
4 7

思路

理解这个算法的关键在于保持 BST 中序遍历的顺序性。

删除一个节点会有三种情况,具体见下面的图解:

用前驱或者后继结点代替被删除结点(Python、Java 代码)

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution:
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
if root is None:
return None

# 递归调用左子树
if key < root.val:
root.left = self.deleteNode(root.left, key)
return root

# 递归调用右子树
if key > root.val:
root.right = self.deleteNode(root.right, key)
return root

# 当前节点的val正好等于key
# 当前节点的左子节点不存在,直接提升右子节点即可
if root.left is None:
new_root = root.right
root.right = None
return new_root

# 当前节点的右子节点不存在,直接提升左子节点即可
if root.right is None:
new_root = root.left
root.left = None
return new_root

# 当前节点的左右子节点均存在,这里我用左子树中最大的点来替换
# 寻找左子树中最大的点(即最右边这个节点)
node = root.left
while node.right != None:
node = node.right
# 左子树中最大的点变为新的根节点
new_root = TreeNode(node.val)
# 新的根节点的左子树需要更新
new_root.left = self.removeMax(root.left)
# 新的根节点的右子树即为原来的右子树
new_root.right = root.right

root.left = None
root.right = None
return new_root

def removeMax(self, node):
if node.right == None:
new_root = node.left
node.left = None
return new_root
node.right = self.removeMax(node.right)
return node

如果不把待删除节点的左右节点设置为None会怎么样?

写这两行代码是出于面向对象的程序语言(Python 和 Java 都是)的垃圾回收机制(Garbage Collection,GC)的考虑。如果一个对象没有被其它对象引用,它会在合适的时候被垃圾回收机制回收,被垃圾回收机制回收即是真正从内存中删除了,语义上也没有必要保留这两个引用。

669-修剪二叉搜索树

题目描述

给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
输入: 
1
/ \
0 2

L = 1
R = 2

输出:
1
\
2

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
输入: 
3
/ \
0 4
\
2
/
1

L = 1
R = 3

输出:
3
/
2
/
1

思路

这里我用递归来进行修建:

  • node.val > R,那么修剪后的二叉树必定出现在节点的左边。
  • node.val < L,那么修剪后的二叉树出现在节点的右边。
  • 否则,我们将会修剪树的两边。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode:
if root == None:
return None

if root.val > R:
return self.trimBST(root.left,L,R)

if root.val < L:
return self.trimBST(root.right,L,R)

if root.val >= L and root.val <= R:
root.left = self.trimBST(root.left,L,R)
root.right = self.trimBST(root.right,L,R)

return root

700-二叉搜索树中的搜索

题目描述

给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。

例如,给定二叉搜索树:

1
2
3
4
5
    4
/ \
2 7
/ \
1 3

和值:2

你应该返回如下子树:

1
2
3
  2     
/ \
1 3

在上述示例中,如果要找的值是 5,但因为没有节点值为 5,我们应该返回 NULL。

思路

根据二叉搜索树的性质:如果val小于当前结点的值,转向其左子树继续搜索;如果val大于当前结点的值,转向其右子树继续搜索;如果已找到,则返回当前结点。如果搜索到最后仍未找到结点,则返回None。

Python实现

方法1:递归

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
if root == None:
return None

if val > root.val:
return self.searchBST(root.right,val)
elif val < root.val:
return self.searchBST(root.left,val)
else:
return root

方法2:迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
if root == None:
return None

while root:
if val > root.val:
root = root.right
elif val < root.val:
root = root.left
elif val == root.val:
return root

return None

701-二叉搜索树中的插入操作

题目描述

给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

例如,给定二叉搜索树:

1
2
3
4
5
    4
/ \
2 7
/ \
1 3

和 插入的值: 5

你可以返回这个二叉搜索树:

1
2
3
4
5
     4
/ \
2 7
/ \ /
1 3 5

或者这个树也是有效的:

1
2
3
4
5
6
7
     5
/ \
2 7
/ \
1 3
\
4

思路

这里我们采用经典的插入方法,使整体操作变化最小。

  1. 直接深拷贝构造新树,然后修改
  2. 寻找到合适的叶位置后插入新节点,这样只需要在原树的某个叶节点处延伸一个节点

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
res = copy.deepcopy(root)
cur_node = res

# 如果二叉搜索树为空树,用val构造二叉树节点作为根节点并返回
if cur_node == None:
return TreeNode(val)

while cur_node:
if val > cur_node.val:
# 走向右子树
if cur_node.right != None:
cur_node = cur_node.right
# 应该走向右子树而右子树为空,即找到了插入位置
else:
cur_node.right = TreeNode(val)
return res
elif val < cur_node.val:
# 走向左子树
if cur_node.left != None:
cur_node = cur_node.left
# 应该走向左子树而左子树为空,即找到了插入位置
else:
cur_node.left = TreeNode(val)
return res

98-验证二叉搜索树

题目描述

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

1
2
3
4
5
输入:
2
/ \
1 3
输出: true

示例 2:

1
2
3
4
5
6
7
8
输入:
5
/ \
1 4
  / \
  3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ,但是其右子节点值为 4

思路

方法1:递归

看到这道题目,我们首先想到遍历整棵树,检查 node.right.val > node.valnode.left.val < node.val 对每个结点是否成立。但是这种方法并不总是正确。因为不仅右子结点要大于该节点,整个右子树的元素都应该大于该节点

这意味着我们需要在遍历树的同时保留结点的上界与下界,在比较时不仅比较子结点的值,也要与上下界比较。

方法2:中序遍历

中序遍历按照左子树 -> 结点 -> 右子树的顺序,这意味着一个二叉搜索树的中序遍历得到的每个元素都应该比下一个元素小

具体步骤:

  1. 计算中序遍历列表inorder
  2. 检查中序遍历列表是否从小到大

Python实现

方法1:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def helper(root,max_val,min_val):
if root == None:
return True

if root.val < max_val and root.val > min_val:
return helper(root.left,root.val,min_val) and helper(root.right,max_val,root.val)


max_val = float('inf')
min_val = -float('inf')
return helper(root,max_val,min_val)

方法2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
if root == None:
return True

pre = -float('inf')
stack = []

p_node = root
while stack or p_node:
# 把所有当前访问节点的左孩子都入栈
while p_node:
stack.append(p_node)
p_node = p_node.left

# 操作栈顶节点,如果是第一次运行到这步,那么这是整棵树的最左节点
cur_node = stack.pop()
# 检查是否从小到大
if cur_node.val > pre:
pre = cur_node.val
else:
return False

# 将指针指向当前节点的右节点
if cur_node.right != None:
p_node = cur_node.right

return True

99-恢复二叉搜索树

题目描述

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下,恢复这棵树。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入: [1,3,null,null,2]

  1
  /
 3
  \
  2

输出: [3,1,null,null,2]

  3
  /
 1
  \
  2

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入: [3,1,4,null,null,2]

3
/ \
1 4
  /
  2

输出: [2,1,4,null,null,3]

2
/ \
1 4
  /
 3

进阶:

  • 使用 O(n) 空间复杂度的解法很容易实现。
  • 你能想出一个只使用常数空间的解决方案吗?

思路

二叉搜索树中序遍历输出应该是递增的,在遍历二叉树的过程中找到不满足递增的点(即错误交换的点),交换两者的值即可。

注意:错误交换的点在中序遍历结果中可能是相邻的,也可能是不相邻的

  • 错误交换的点是相邻的(中序遍历结果1324):使用first和second表示错误交换的两个点,在第一次遇到不递增的情况时,将first置为3,second置为2,遍历结束后交换first与second。
  • 错误交换的点是不相邻的(中序遍历结果3214):在第一次遇到不递增的情况时,将first设置为3,second设置为2,在第二次遇到不递增的情况时,只改变second,将second置为1.遍历结束后交换first与second。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
def recoverTree(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if root == None:
return None

pre = TreeNode(-float('inf'))
first_node = None
second_node = None

stack = []
p_node = root
while stack or p_node:
while p_node:
stack.append(p_node)
p_node = p_node.left

cur_node = stack.pop()

# 根据当前节点和前一个节点的值来判断节点是否错误
if cur_node.val > pre.val:
pre = cur_node
else:
# 第一次相遇
if first_node == None:
first_node = pre
second_node = cur_node
# 第二次相遇
else:
second_node = cur_node

if cur_node.right != None:
p_node = cur_node.right

# 交换两个错误交换的节点
first_node.val,second_node.val = second_node.val,first_node.val

230-二叉搜索树中第K小的元素

题目描述

给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明:你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

1
2
3
4
5
6
7
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
  2
输出: 1

示例 2:

1
2
3
4
5
6
7
8
9
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3

进阶:如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化 kthSmallest 函数?

思路

二叉搜索树的中序遍历序列为递增序列,因此可中序遍历二叉搜索树,返回第K个元素。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
if root == None:
return None

# 中序遍历二叉树
res = []
stack = []
p_node = root

while stack or p_node:
while p_node:
stack.append(p_node)
p_node = p_node.left

cur_node = stack.pop()
res.append(cur_node.val)

if cur_node.right != None:
p_node = cur_node.right

# 返回第k个元素
return res[k-1]

我们也可以提前中止中序遍历:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
if root == None:
return None

# 中序遍历二叉树
stack = []
p_node = root

while stack or p_node:
while p_node:
stack.append(p_node)
p_node = p_node.left

cur_node = stack.pop()

# 返回第k个元素
k -= 1
if k == 0:
return cur_node.val

if cur_node.right != None:
p_node = cur_node.right

501-二叉搜索树中的众数

题目描述

给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。

假定 BST 有如下定义:

  • 结点左子树中所含结点的值小于等于当前结点的值
  • 结点右子树中所含结点的值大于等于当前结点的值
  • 左子树和右子树都是二叉搜索树

例如:

1
2
3
4
5
6
7
8
给定 BST [1,null,2,2],

1
\
2
/
2
返回[2].

提示:如果众数超过1个,不需考虑输出顺序

进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)

思路

方法1:层序遍历+字典

这里我用层次遍历,然后用一个字典记录每个值出现的次数,最后在字典中搜索最大值(即出现次数最多的值,也就是众数)。

但是这种方法用了额外的空间。

方法2:中序遍历

二叉搜索树的中序遍历是一个升序序列,逐个比对当前结点值cur_node.val与前驱结点值pre_node.val。更新当前节点值出现次数curTimes及最大出现次数maxTimes,更新规则:

  • curTimes=maxTimes,将cur_node.val添加到结果向量res
  • curTimes>maxTimes,清空res,将cur_node.val添加到res,并更新maxTimescurTimes

Python实现

方法1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
def findMode(self, root: TreeNode) -> List[int]:
if root == None:
return None

dicts = {}
queue = [root]
while queue:
length = len(queue)
for _ in range(length):
node = queue.pop(0)
# 节点值存入字典
if node.val in dicts:
dicts[node.val] += 1
else:
dicts[node.val] = 1

if node.left != None:
queue.append(node.left)
if node.right != None:
queue.append(node.right)

# 计算众数
max_num = 0
for i,counts in dicts.items():
if counts > max_num:
res = [i]
max_num = counts
# 输出所有众数
elif counts == max_num:
res.append(i)

return res

方法2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
def findMode(self, root: TreeNode) -> List[int]:
if root == None:
return None

stack = []
p_node = root
pre_node = TreeNode(float('inf'))
maxTimes = 0
res = []

while stack or p_node:
# 把所有当前访问节点的左孩子都入栈
while p_node != None:
stack.append(p_node)
p_node = p_node.left

cur_node = stack.pop()

# 更新当前节点出现次数
if pre_node.val == cur_node.val:
curTimes += 1
else:
curTimes = 1
# 最大出现次数
if maxTimes == curTimes:
res.append(cur_node.val)
elif maxTimes < curTimes:
res = [cur_node.val]
maxTimes = curTimes

# 更新前驱节点
pre_node = cur_node

if cur_node.right != None:
# 将指针指向当前节点的右节点
p_node = cur_node.right

return res

参考

赞赏一杯咖啡
0%