Leetcode 669. 修剪二叉搜索树 Trim a Binary Search Tree - Python 以递归法解题

一、解题思路

递归三部曲

1. 递归结束条件当遇到空节点返回None
2. 递归返回值、参数
3. 单层递归逻辑将每个root.val与low、high比较比low小的节点用同样方法递归右子树比high大大节点递归其左子树。
4. 难点不符合条件的节点<low or > high会将另一侧符合条件的节点树赋值给其上一个节点左或右子树

# 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 None
        if root.val < low: return self.trimBST(root.right, low, high)
        if root.val > high: return self.trimBST(root.left, low, high)

        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

引用

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.md