代码随想录学习Day 20

669.修剪二叉搜索树

题目链接

讲解链接

思路：采用递归方法，若root.val > high，判断左子树是否为空，若不空，递归遍历左子树，若空就返回null；若root.val < low，则判断右子树是否为空，若不空就递归遍历右子树，若空就返回null；如果low <= root.val <= high，就递归遍历左右子树，最后返回根节点即可。

递归三部曲：

1.递归函数参数及返回值：参数就是当前节点，边界值low，high。返回值为修剪后的二叉搜索树的根节点。

def trimBST(self, root, low, high):

2.递归终止条件：遇到空则返回

if not root:
    return None

3.单层递归逻辑：若当前节点小于low，则遍历其左子树；大于high则遍历其右子树。之后将下一层处理完左右子树的结果返回给当前根节点的左右孩子，最后返回root节点。

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

完整代码如下：

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root:  # 若为空则返回None
            return None
        if root.val < low:  # 小于low则返回其右子树修剪后的结果
            return self.trimBST(root.right, low, high)  # 注意这里不能直接返回root.right，因为以root.right为根节点的树不一定符合区间条件，需要进行递归修剪
        elif root.val > high:  # 大于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

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

题目链接

讲解链接

思路：构造二叉树一般考虑前序遍历的方式。本题由于要构造的是一颗平衡二叉搜索树，所以要选取数组最中间的元素来作为根节点，然后两边的元素递归构造左右子树，这样才能保证左右子树的高度相差不超过1。代码则与之前做过的构造最大二叉树类似，只需将求最大元素改为求最中间元素即可。

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:  # 数组为空则返回空
            return None
        mid = len(nums) // 2  # 找数组最中间的元素
        root = TreeNode(nums[mid])  # 最中间元素作为根节点->中
        root.left = self.sortedArrayToBST(nums[:mid])  # 递归构造左子树->左
        root.right = self.sortedArrayToBST(nums[mid+1:])  # 递归构造右子树->右
        return root  # 返回根节点

538.把二叉搜索树转换为累加树

题目链接

讲解链接

将本题换一个角度来看，就是对一个有序数组[2, 5, 13]求其从后到前的累加数组，也就是[20, 18, 13]。在二叉搜索树中最右下角的元素是最大的，所以遍历顺序应该是右中左（反中序遍历），从最大的元素开始，每个节点的值为当前值与前一个节点的值的和。

递归三部曲：

1.递归函数参数及返回值：参数就是当前遍历的节点，不需要返回值，但需要定义一个全局变量pre来保存当前节点前一个节点的值。

def __init__(self):
    self.pre = 0
def traversal(self, root):

2.递归终止条件：遇到空则直接返回。

if not cur:
    return

3.单层递归逻辑：进行反中序遍历，先遍历右子树，再遍历左子树，将每个节点的值改为其当前值与pre值的和。

self.traversal(cur.right)
cur.val += self.pre
self.pre = cur.val
self.traversal(cur.left)

整体代码如下：

class Solution:
    def __init__(self):
        self.pre = 0  # 定义pre让其保存cur的前一个节点的值，初始为0
    def traversal(self, cur):
        if not cur:  # 遇到空则返回
            return
        self.traversal(cur.right)  # 右
        cur.val += self.pre  # 改变节点值
        self.pre = cur.val  # pre=当前节点的值
        self.traversal(cur.left)  # 左
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.traversal(root)
        return root