LeetCode 669.修剪二叉搜索树：
文章链接
题目链接：669.修剪二叉搜索树
思路：
- 递归
因为二叉搜索树为有序树，因此
若node.val < low，需要删除node及左子树
若node.val > high，需要删除node及右子树
① 参数及返回值：传入node, low, high，需要返回删除后的新节点
② 边界条件：空结点
③ 单层递归逻辑：判断node.val的值是否在[low, high]中，若不在，一定会删除node的一棵子树，因此只递归另一个子树；否则两棵子树都要递归
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if not root:
print("None")
return None
#print("node.val: " + str(root.val))
if root.val < low: # 移除root结点和左子树
#print("remove root and left")
right = self.trimBST(root.right, low, high)
return right
elif root.val > high: # 移除root结点和右子树
#print("remove root and right")
left = self.trimBST(root.left, low, high)
return left
#print("noremove root")
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root
- 迭代
需要对二叉搜索树的有序性更进一步的使用。
如果root.val在[low, high]中，那么删除左子树中的结点只可能为node.val < low，删除右子树中的结点只可能为node.val > high；并且遍历二叉搜索树过程中不需要进行回溯，一直向下遍历即可。（但是左右都要遍历一次，因此左右子树分开遍历）
因此第一步为修改root结点，使得root.val在[low, high]中。
需要注意的是：使用的是待删除结点的parent结点进行遍历，parent.val在[low, high]中，因此可以一直先判断parent.left / parent.right是否符合范围，再向左/向右遍历。因此如果删除了结点，不能更新parent
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if not root:
return None
# 将root的范围划到[low, high]之中
while root and (root.val < low or root.val > high):
if root.val < low: root = root.right
else: root = root.left
# 再来处理左子树，root.val 在[low, high]
cur = root
if root: print("root.val: " + str(root.val))
# 删除左子树中的结点只可能是cur.left.val < low
while cur: # 使用待删除结点的parent结点进行遍历
print("cur.val: " + str(cur.val))
if cur.left and cur.left.val < low:
print("delete cur.left")
cur.left = cur.left.right # 删除结点后，cur.left不一定在[low, high]中，因此不更新cur
else:
cur = cur.left
# 处理右子树，删除右子树结点只可能cur.right.val > high
cur = root
while cur:
print("cur.val: " + str(cur.val))
if cur.right and cur.right.val > high:
print("delete cur.right")
cur.right = cur.right.left
else:
cur = cur.right
return root
感悟：
递归时需要注意到，若一个结点的值不在范围内，需要删除结点和一棵子树。
迭代比较难想到，如果是没有接触过的，要从哪个地方入手呢。
对二叉搜索树有序的利用
LeetCode 108.将有序数组转换为二叉搜索树：
文章链接
题目链接：108.将有序数组转换为二叉搜索树
思路：
使用有序数组构造平衡二叉搜索树，因为题目中已经给定了升序数组，需要构造平衡二叉搜索树，因此使用数组的中值作为根节点的值，左右部分分别构造左子树和右子树
需要注意的是，使用数组构造时，采用的左闭右闭区间还是左闭右开区间
- 递归
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if nums == []:
return None
root = self.traversal(nums, 0, len(nums) - 1)
return root
def traversal(self, nums, left, right):
if left > right: # 双闭区间
return None
mid = left + (right - left) // 2 # 使用中值作为根结点值
node = TreeNode(val=nums[mid])
node.left = self.traversal(nums, left, mid - 1) # 构造并连接左子树
node.right = self.traversal(nums, mid + 1, right) # 构造并连接右子树
return node
- 迭代
使用三个队列实现，分别保存遍历的结点，结点值所在区间的左端点和结点所在区间的右端点。
遍历的结点可以是只初始化等待赋值的结点，也可以是已经赋值等待构造左右孩子结点的结点。下列代码中采用第一种。
构造过程中容易忘记连接左右孩子结点和根结点
from collections import deque
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if nums == []:
return None
nodeQue = deque() # 保存遍历的结点，或者说要被赋值的结点
leftQue = deque() # 保存左区间
rightQue = deque() # 保存右区间
root = TreeNode()
nodeQue.append(root)
leftQue.append(0)
rightQue.append(len(nums) - 1) # 双闭区间
while nodeQue:
cur = nodeQue.popleft()
left, right = leftQue.popleft(), rightQue.popleft()
mid = left + (right - left) // 2
cur.val = nums[mid] # 当前结点赋值
if left <= mid - 1: # 进队左孩子结点
cur.left = TreeNode() # 容易忘记
nodeQue.append(cur.left)
leftQue.append(left)
rightQue.append(mid - 1)
if right >= mid + 1: # 进队右孩子结点
cur.right = rightNode # 容易忘记
nodeQue.append(cur.right)
leftQue.append(mid + 1)
rightQue.append(right)
return root
感悟：
迭代使用队列来构造平衡二叉搜索树，需要清楚入队的结点是赋值前还是赋值后的，同时记得连接左右孩子结点。
LeetCode 538.把二叉搜索树转换为累加树：
文章链接
题目链接：538.把二叉搜索树转换为累加树
思路：
需要注意node的新值等于原树中大于或等于node.val的值之和，>=node.val的结点并不只有node的右子树。比如下图
又二叉搜索树进行中序遍历（左根右）为升序数组，因此只需要对二叉搜索树进行右根左遍历得到降序数组，同时遍历时对结点的值进行相加和赋值，就得到了累加树
"""
使用双指针，pre指向前一个结点
"""
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
pre, cur = None, root
stack = []
while cur or stack:
if cur:
stack.append(cur)
cur = cur.right # 右
else:
cur = stack.pop()
if pre:
cur.val += pre.val
pre = cur # 记得更新pre
cur = cur.left # 左
return root
"""
使用count计数，记录遍历到node前的结点的值的加和
"""
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
self.count = 0
self.traversal(root)
return root
def traversal(self, node):
if not node:
return
self.traversal(node.right) # 右
self.count += node.val
node.val = self.count # 根
self.traversal(node.left) # 左
感悟：
使用双指针时需要记得更新pre，以及二叉搜索树中 >node.val的结点不只有node的右子树
二叉树的总结：
文章链接
图的链接