669. 修剪二叉搜索树
- 思路
- example
- 树中每个节点的值都是 唯一 的
- 递归
- 返回值：修剪好的当前树的头节点
- 节点值 < low: 删去节点以及左子树，链接母节点到右子树（递归实现），继续递归遍历
- 节点值 > high: 删去节点以及右子树，链接母节点到左子树（递归实现），继续递归遍历
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
def traversal(root):
if root == None:
return None
if root.val < low:
return traversal(root.right)
if root.val > high:
return traversal(root.left)
# root.val 保留
root.left = traversal(root.left)
root.right = traversal(root.right)
return root
return traversal(root)
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if root == None:
return None
if root.val == low:
root.left = None
root.right = self.trimBST(root.right, low, high) # 右子树也需要trim
return root
if root.val == high:
root.right = None
root.left = self.trimBST(root.left, low, high) # 左子树也需要trim
return root
if root.val < low:
return self.trimBST(root.right, low, high)
if root.val > high:
return self.trimBST(root.left, low, high)
if low < root.val and root.val < high:
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root
- 迭代
TBA
108. 将有序数组转换为二叉搜索树
- 思路
- example
- 高度平衡
- nums 按 严格递增 顺序排列
- 递归
- "通过递归函数的返回值来增删二叉树"
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def traversal(nums, left, right):
if left > right:
return None
mid = left + (right - left) // 2
root = TreeNode(nums[mid])
root.left = traversal(nums, left, mid - 1)
root.right = traversal(nums, mid + 1, right)
return root
return traversal(nums, 0, len(nums)-1)
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
n = len(nums)
if n == 0:
return None
mid = 0 + (n-1 - 0) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root
538. 把二叉搜索树转换为累加树
- 思路
- example
- 树的节点值各不相同
- 遍历：右中左
- 维护全局变量pre或者sum_
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def traversal(root):
nonlocal sum_
if root == None:
return
traversal(root.right)
root.val += sum_
sum_= root.val
traversal(root.left)
sum_ = 0
traversal(root)
return root
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def traversal(root):
nonlocal cum_sum
if root == None:
return
traversal(root.right)
root.val += cum_sum
cum_sum = root.val
traversal(root.left)
cum_sum = 0
traversal(root)
return root
- 维护Pre节点
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def traversal(root):
nonlocal pre
if root == None:
return
traversal(root.right)
if pre:
root.val += pre.val
pre = root
traversal(root.left)
pre = None
traversal(root)
return root
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def traverse(root):
nonlocal pre
if root == None:
return
traverse(root.right)
if pre:
root.val += pre.val
pre = root # !!!
traverse(root.left)
pre = None
traverse(root)
return root
** 总结 **
- 遍历：
- 深度：前，中，后 （递归，迭代(栈））
- 广度：层序：迭代 (deque)
- 深度
- 节点数
- 对称
- 平衡
- 路径
- 左下角
- 构造 （二叉树或二叉搜索树），先构造中节点。
- 翻转
- 合并
- 删除
- 插入
- 搜索树 （中序）
- 普通二叉树属性：后序
- 搜索二叉树属性：中序
-
链接
image
