代码随想录算法训练营第二十三天 | LeetCode669 修剪二叉树、LeetCode108 将有序数组转换为二叉搜索树、LeetCode538 将二叉搜索树转换为累加树

今日任务：

LeetCode669 修剪二叉树
LeetCode108 将有序数组转换为二叉搜索树
LeetCode538 将二叉搜索树转换为累加树
二叉树部分总结

资料来源：

1 LeetCode669 修剪二叉树

题目

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在唯一的答案。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：


输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：


输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

提示：

树中节点数在范围 [1, 104] 内
0 <= Node.val <= 104
树中每个节点的值都是唯一的
题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 104

剪枝剪了半天也没剪明白，直接看了代码随想录。递归写法还是按递归三要素走的，如果到了空节点就停止递归。单层递归里，如果当前处理的节点不符合条件，就往可能符合条件的子树里去找：大于high就往左子树递归，小于low就往右子树递归，直接返回递归的结果，当前处理的不符合条件节点就没了；如果当前处理的节点符合条件，那就往左右子树去递归，返回当前节点就好。

python
from typing import Optional

# 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]:
        return self.recursion(root, low, high)

    def recursion(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if root is None:  # 终止条件
            return None
        # 单层递归的逻辑
        # 当前节点不符合条件的话就处理
        if root.val < low:
            return self.recursion(root.right, low, high)  # 返回的是子树的查找结果 接住结果的是当前节点的上一层节点 当前这个不符合条件的节点就删掉了
        if root.val > high:
            return self.recursion(root.left, low, high)
        # 如果当前节点符合条件
        root.left = self.recursion(root.left, low, high)
        root.right = self.recursion(root.right, low, high)
        return root

还有一个迭代版本，说实话挺不好想的，也挺不好写的。

python
from typing import Optional

# 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]:
        # 先将root移动到区间里
        while root is not None and (root.val > high or root.val < low):
            if root.val > high:
                root = root.left
            else:
                root = root.right

        # 移动完了 处理左右子树
        pointer = root
        while pointer is not None:
            while pointer.left is not None and pointer.left.val < low:  # pointer.left不符合条件
                pointer.left = pointer.left.right  # 将左子树的右子树接过来 接着循环判断
            pointer = pointer.left

        pointer = root
        while pointer is not None:
            while pointer.right is not None and pointer.right.val > high:
                pointer.right = pointer.right.left
            pointer = pointer.right

        return root

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

题目

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

示例 1：


输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案

示例 2：


输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按严格递增顺序排列

这道题的思路和前几天做过的一道题思路特别像。平衡二叉树么，要求子树高度差不能超过1，那我创建两个子树的时候平分目前有的节点不就行了，这就是这道题的整体思路。

python
from typing import List, Optional

# 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.nums = None

    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if len(nums) == 1:
            return TreeNode(val=nums[0])
        self.nums = nums
        return self.recursion(len(nums) - 1, 0)

    def recursion(self, high: int, low: int) -> Optional[TreeNode]:
        if high < low:
            return None
        root = int((high + low) / 2)
        root_node = TreeNode(val=self.nums[root])
        root_node.right = self.recursion(high, root + 1)
        root_node.left = self.recursion(root - 1, low)
        return root_node

3 LeetCode538 将二叉搜索树转换为累加树

题目

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：


输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：


输入：root = [0,null,1]
输出：[1,null,1]

示例 3：


输入：root = [1,0,2]
输出：[3,3,2]

示例 4：


输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值互不相同。
给定的树为二叉搜索树。

反向中序秒了。

python
from collections import deque
from typing import Optional

# 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]:
        if root is None:
            return None
        stack = deque()
        node = root
        stack.append(node)
        sum = 0
        while len(stack) != 0:
            node = stack.pop()
            if node is None:
                node = stack.pop()
                sum += node.val
                node.val = sum
            else:
                if node.left is not None:
                    stack.append(node.left)
                stack.append(node)
                stack.append(None)
                if node.right is not None:
                    stack.append(node.right)
        return root

4 二叉树部分总结

嫖张图过来吧，别的感觉好像也没什么可以总结的了。个人觉得比较重要的点如下，之后二刷还有的话再补充：

统一写法风格的前中后序遍历二叉树，那个记下来之后用起来真的很方便。
对搜索二叉树，就把它看成一个有序数组去想，在不少的场合能够加速思考过程。反正对它中序遍历就是有序数组了。
如果题目对树的结构要求比较高（或者说节点的位置关系），那么优先考虑递归。
递归三件套：递归函数参数和返回值、终止条件、单层递归顺序。

目录

1 LeetCode669 修剪二叉树

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

3 LeetCode538 将二叉搜索树转换为累加树

4 二叉树部分总结