Okii's blog

仅作为记录自己的学习过程

0%

Leetcode 二叉搜索树

发表于 分类于
本文字数： 7.5k 阅读时长 ≈ 14 分钟

Leetcode刷题记录——二叉搜索树

Leetcode700 二叉搜索树中的搜索

首先明白二叉搜索树的性质：

二叉搜索树是一个有序树：

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉搜索树

还是递归三部曲：

1、确定递归函数的参数和返回值

递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点

2、确定终止条件

如果当前root为空，或者找到这个数值了，就返回root节点

3、确定单层递归的逻辑

因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。

如果root.val > val，搜索左子树，如果root.val < val，就搜索右子树，最后如果都没有搜索到，就返回None。

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return None
        if root.val == val:
            return root
        elif root.val < val:
            return self.searchBST(root.right, val)
        else:
            return self.searchBST(root.left, val)

Leetcode98 验证二叉搜索树

利用二叉搜索树的性质，使用中序遍历所有节点，并存入数组res

最后遍历res，看是否是递增的数组

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        res = []
        return self.traversal(root, res)
    def traversal(self, root, res):
        if not root:
            return True
        self.traversal(root.left, res)
        res.append(root.val)
        self.traversal(root.right, res)
        for i in range(len(res)-1):
            if res[i] >= res[i+1]:
                return False
        return True

Leetcode530 二叉搜索树的最小绝对差

最直观的想法是，跟上一题一样中序遍历整棵二叉搜索树，得到一个递增数组。再找出相邻节点的绝对差(因为数组已经是有序的，最小绝对差肯定在相邻节点出现)

为了减少空间消耗，也可以在遍历的时候就计算出相邻节点的绝对差

需要用一个pre节点记录一下cur节点的前一个节点

1
2
3
4
self.pre = None
if self.pre:
    self.result = min(self.result, cur.val-self.pre.val)
self.pre = cur

很巧妙地使得pre记录cur节点的前一个节点

剩下的就还是递归三部曲：

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.result = float('inf')
        self.pre = None
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        self.tarversal(root)
        return self.result
    def tarversal(self, cur):
        if not cur:
            return
        self.tarversal(cur.left)
        # 当cur第一次遍历到左叶节点时，pre还是None，不进入逻辑
        if self.pre:
            self.result = min(self.result, cur.val-self.pre.val)
        # 下一次pre就能指向之前的cur了
        self.pre = cur
        self.tarversal(cur.right)

Leetcode501 二叉搜索树中的众数

首先能想到的是一个比较简单的思路，通用，不只是二叉搜索树，普通树也可以用

用中序遍历(什么遍历方式都可以)，将遍历得到的元素以及次数放入一个map

最后对map的值进行排序，得到次数最多的几个元素

不用额外空间的话，考虑与上一道题一样的双指针思路

留到下次做的时候再来写

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        map = {}
        self.traversal(root, map)
        sorted_map = sorted(map.items(), key=lambda x: x[1], reverse=True)
        res = []
        max_value = sorted_map[0][1]
        for key, value in sorted_map:
            if value == max_value:
                res.append(key)
        return res
    def traversal(self, root, map):
        if not root:
            return 
        self.traversal(root.left, map)
        map[root.val] = map.get(root.val, 0) + 1
        self.traversal(root.right, map)

Leetcode236 二叉树的最近公共祖先

如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先

判断逻辑是：如果递归遍历遇到q，就将q返回，遇到p 就将p返回，那么如果左右子树的返回值都不为空，说明此时的中节点，一定是q 和p 的最近祖先

但是容易忽略一个情况：节点本身p(q)，它拥有一个子孙节点q(p)

其实上述两种情况的代码实现过程都是一样的，也可以说，实现情况一的逻辑，顺便包含了情况二

因为遇到 q 或者 p 就返回，这样也包含了 q 或者 p 本身就是公共祖先的情况

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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 not root:
            return None
        if root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        if not left and right:
            return right
        if left and not right:
            return left
        if not left and not right:
            return None

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

上一题的解题思路完全也可以做

但二叉搜索树由于其特性

1、如果当前根节点的值均大于p和q的val，那么最近公共祖先一定在其左子树

2、如果当前根节点的值均小于p和q的val，那么最近公共祖先一定在其右子树

3、如果当前根节点的值在p和q的val之间，那么该节点就是最近公共祖先

再利用递归去解题即可

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 not root:
            return None
        if root.val > p.val and root.val > q.val:
            left = self.lowestCommonAncestor(root.left, p, q)
            if left:
                return left
        if root.val < p.val and root.val < q.val:
            right = self.lowestCommonAncestor(root.right, p, q)
            if right:
                return right
        return root

Leetcode701 二叉搜索树中的插入操作

由于二叉搜索树的特点，插入永远可以在某个叶子节点的位置

只需要一直查找就行，找到了就插入

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val=val)
        cur = root
        while cur:
            temp = cur
            if val > cur.val:
                cur = cur.right
            else:
                cur = cur.left
        if val < temp.val:
            temp.left = TreeNode(val=val)
        if val > temp.val:
            temp.right = TreeNode(val=val)
        return root

Leetcode538 把二叉搜索树转换为累加树

还是利用二叉树中的双指针套路，cur和pre的用法，要熟练

根据题目性质，很容易看出是要右中左地去遍历整棵树，再遍历时修改节点的值即可

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.pre = 0
        self.traversal(root)
        return root
    def traversal(self, cur):
        if not cur:
            return
        self.traversal(cur.right)
        if self.pre != 0:
            cur.val = cur.val + self.pre
        else:
            cur.val = cur.val
        self.pre = cur.val
        self.traversal(cur.left)

Leetcode450 删除二叉搜索树中的节点

对于删除节点，有5种情况

1、找不到该节点

2、删除节点为叶子节点

3、删除节点左子树为空，右子树不为空

4、删除节点右子树为空，左子树不为空

5、删除节点的左右子树均不为空

在处理终止条件时，就要处理删除的逻辑

在接下来的左右子树递归中，去接住递归的返回值(也就是处理完删除节点后的左右子树)

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return root
        if root.val == key:
            if not root.left and not root.right:
                return None
            elif not root.left and root.right:
                return root.right
            elif root.left and not root.right:
                return root.left
            else:
                cur = root.right
                while cur.left:
                    cur = cur.left
                cur.left = root.left
                return root.right
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        return root

Leetcode669 修剪二叉搜索树

利用二叉搜索树的性质

很好做题，不要陷入误区，子树需要递归地去判断有没有要删的节点

如果当前节点不符合条件，不能直接删了，可能左右子树中还有符合条件的节点

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root:
            return root
        if root.val < low:
            right = self.trimBST(root.right, low, high)
            return right
        if root.val > high:
            left = self.trimBST(root.left, low, high)
            return left
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

Leetcode108 将有序数组转换为二叉搜索树

用二分的思想，就能达到平衡的效果

再用前序的思想递归的构建即可

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        left = 0
        right = len(nums) - 1
        mid = left + (right-left) // 2
        root = TreeNode(val = nums[mid])
        nums_left = nums[:mid]
        nums_right = nums[mid+1:]
        root.left = self.sortedArrayToBST(nums_left)
        root.right = self.sortedArrayToBST(nums_right)
        return root