LeetCodeCampsDay21
LeetCodeCampsDay21二叉树part08
平衡二叉树的构造；修剪二叉树（难度甚至比删除二叉树的节点要简单一些）
669. 修剪二叉搜索树
https://leetcode.cn/problems/trim-a-binary-search-tree/
给你二叉搜索树的根节点 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
递归思路
- 使用递归，带返回值，返回的是修剪后的子树节点；
- 输入节点/low以及high，输出是修剪后的子树节点；
- 终止条件，如果输入节点为空就返回
- 单层逻辑：修剪的规则是，如果node.val<low，则node需要被删除，并且node.right会被当成node返回给node的父节点（并且node.left肯定都小于low，都被修剪了）；如果node.val> high,，则node需要被删除，并且node.left会被当成node返回给node的父节点（并且node.right都大于high，都被修剪了）
递归代码
- 时间复杂度O(N)
- 空间复杂度O(H)
# 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 foo(self, node, low, high) -> TreeNode:
# 使用递归，带返回值，返回的是修剪后的子树节点
if not node:
return None
if node.val < low:
# 若node.val小于low，说明node是需要被删除的，但node.right可能不会被删除
# 这里直接返回了node.right，说明node已经被修剪了
return self.foo(node.right, low, high)
if node.val > high:
return self.foo(node.left, low, high)
# 这里是将修剪好的子树上传上来
node.left = self.foo(node.left, low, high)
node.right = self.foo(node.right, low, high)
return node
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
# 使用递归完成
return self.foo(root, low, high)108. 将有序数组转换为二叉搜索树
https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
给你一个整数数组 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] <= 104nums按 严格递增 顺序排列
递归思路
- 使用递归，带返回值，输出排序后的子树节点
- 输入num(list)，输出这个nums的树
- 终止条件num为空
- 单层逻辑：先找到这个nums里的medium值（就是len(nums)//2），如果len为偶数，选择哪个都可以；以这个medium为root，然后递归地构造root的左、右子树；这个方法与之前构造最大子树（654. 最大二叉树）有点像。
递归代码
- 时间复杂度O(N)
- 空间复杂度O(H)
# 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:
# 找到中间位置的节点当成root，再以中间节点划分左、右区间进行递归地建树
def foo(self, nums: List[int]) -> TreeNode:
if len(nums) == 0:
return None
L = len(nums)
midIndex = L // 2
root = TreeNode(nums[midIndex])
root.left = self.foo(nums[:midIndex])
root.right = self.foo(nums[midIndex + 1:])
return root
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
# 递归
return self.foo(nums)538. 把二叉搜索树转换为累加树
https://leetcode.cn/problems/convert-bst-to-greater-tree/
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（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之间。 - 树中的所有值 互不相同 。
- 给定的树为二叉搜索树。
递归思路
因为本题为BST，它本身就有了顺序，可以先做一次反中序遍历，再将中间节点更新为node.val += pre.val，其中pre.val就是反中序遍历中较大的节点的累加值
- 使用不带返回值的递归
- 输入node节点，无输出
- 终止条件，当前节点为空，直接返回
- 单层逻辑：使用反中序遍历，对中间节点进行更新，更新成node.val = node.val + pre.val
递归代码
- 时间复杂度O(N)
- 空间复杂度O(H)
# 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.pre = TreeNode(0)
def foo(self, node):
if not node:
return
if node.right:
self.foo(node.right)
node.val += self.pre.val
self.pre = node
if node.left:
self.foo(node.left)
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# 思路1 把中序遍历，逐个累加，需要有个pre节点
self.foo(root)
return root
迭代思路
- 使用反中序遍历，先一路干到最右节点（把一路上的节点都添加到stack中），再逐个弹出，弹出的顺序就是（右、中、左）即完成反中序遍历；对中间节点进行操作，修改它的值为node.val += pre.val（注意，从python机制上来说，使用+=是原地赋值而使用val = val + pre会新增空间）
迭代代码
- 时间复杂度O(N)
- 空间复杂度O(H)
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# 思路1 把中序遍历，逐个累加，需要有个pre节点
# self.foo(root)
# return root
# 使用栈+迭代实现反中序遍历
stack = list()
if not root:
return root
cur = root
pre = TreeNode(0)
while stack or cur:
if cur:
stack.append(cur)
# 先干到最右节点
cur = cur.right
else:
# 最右节点
cur = stack.pop()
# 中节点
cur.val += pre.val
pre = cur
# 左节点
cur = cur.left
return root- 文章作者:
- Lthero博客
- 版权声明:
- 本博客所有文章除特别声明外，均采用CC BY-NC-SA 4.0许可协议。转载请注明来自 Lthero博客！
