原题链接:
https://leetcode.cn/problems/trim-a-binary-search-tree/
比较好的一道递归
后序遍历的思路 先处理好下面的结点然后依次返回结果
处理方式 按照bst的定义
1.如果node为空 直接返回
2.如果右子树为空 直接返回左子树
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
# 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]:
        def dfs(node):
            if not node:
                return
            node.left = dfs(node.left)
            node.right = dfs(node.right)
            v = node.val
            # bst 删除节点的套路是相同的
            # 不要往上看 就是将其左子树 接在右子树最左侧即可
            if v < low or v > high:
                cur = node.right
                # 如果右子树为空 则直接返回左子树
                if not cur:
                    return node.left
                tmp = cur 
                while cur.left:
                    cur = cur.left
                cur.left = node.left
                return tmp
            else:
                return node

        root = dfs(root)
        return root