代码随想录 - Day30 - 修剪二叉树，转换二叉树 + 二叉树总结

代码随想录 - Day30 - 修剪二叉树，转换二叉树 + 二叉树总结

669. 修剪二叉搜索树

有点像是删除二叉搜索树的变形，改变了删除条件而已。
递归法：

class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if not root:return rootif root.val < low:      # 当前节点小于low，不用再看其左子树，遍历其右子树即可right = self.trimBST(root.right, low, high)return rightif root.val > high:     # 当前节点大于high，不用再看其右子树，遍历其左子树即可left = self.trimBST(root.left, low, high)return leftroot.left = self.trimBST(root.left, low, high)      # root.left接入符合条件的左孩子root.right = self.trimBST(root.right, low, high)    # root.right接入符合条件的右孩子return root

迭代法：

'''
在剪枝的时候，可以分为三步：
将root移动到[L, R] 范围内，注意是左闭右闭区间
剪枝左子树
剪枝右子树
'''
class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if not root:return root# 处理头节点，把头结点放到[low, high]范围内while root and (root.val < low or root.val > high):if root.val < low:      # 小于low往右走root = root.rightelse:                   # 大于high往左走root = root.leftcurleft, curright = root, root# 处理左孩子元素小于low的情况while curleft:while curleft.left and curleft.left.val < low:curleft.left = curleft.left.rightcurleft = curleft.left# 处理右孩子元素大于high的情况while curright:while curright.right and curright.right.val > high:curright.right = curright.right.leftcurright = curright.rightreturn root

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

对于奇数长度的数组可以直接取中点，对于偶数长度的数组则需要用mid = int(left + ((right - left) / 2))。
中点作为根节点，左右两侧则分别为左子树和右子树，依次进行递归遍历。

class Solution:# 左闭右闭区间[left, right]def traversal(self, nums, left, right):if left > right:return Nonemid = int(left + ((right - left) / 2))      # 防止越界root = TreeNode(nums[mid])root.left = self.traversal(nums, left, mid - 1)root.right = self.traversal(nums, mid + 1, right)return rootdef sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:root = self.traversal(nums, 0, len(nums) - 1)return root

迭代法：用队列模拟递归过程

from collections import dequeclass Solution:def sortedArrayToBST(self, nums: List[int]) -> TreeNode:if len(nums) == 0:return Noneroot = TreeNode(0)  # 初始根节点nodeQue = deque()   # 放遍历的节点leftQue = deque()   # 保存左区间下标rightQue = deque()  # 保存右区间下标nodeQue.append(root)               # 根节点入队列leftQue.append(0)                  # 0为左区间下标初始位置rightQue.append(len(nums) - 1)     # len(nums) - 1为右区间下标初始位置while nodeQue:curNode = nodeQue.popleft()left = leftQue.popleft()right = rightQue.popleft()mid = left + (right - left) // 2curNode.val = nums[mid]     # 将mid对应的元素给中间节点if left <= mid - 1:         # 处理左区间curNode.left = TreeNode(0)nodeQue.append(curNode.left)leftQue.append(left)rightQue.append(mid - 1)if right >= mid + 1:        # 处理右区间curNode.right = TreeNode(0)nodeQue.append(curNode.right)leftQue.append(mid + 1)rightQue.append(right)return root

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

题目中的累加是右中左的顺序进行累加，从最大的节点值累加到最小的节点值。
所以要反中序遍历该二叉树，然后顺序累加。
需要一个pre指针记录当前节点的前一个节点，这样才能方便累加。

class Solution:def traversal(self, cur):       # 右中左遍历if not cur:                 # 终止条件returnself.traversal(cur.right)   # 右cur.val += self.pre         # 中self.pre = cur.valself.traversal(cur.left)    # 左def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:self.pre = 0                # 记录前一个节点的数值self.traversal(root)return root

或者写成这样也可以：

class Solution:def __init__(self):               # 记录前一个节点的数值self.pre = 0def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root:                  # 终止条件returnself.convertBST(root.right)   # 右root.val += self.pre          # 中self.pre = root.valself.convertBST(root.left)    # 左return root

迭代法：

class Solution:def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root: return rootstack = []result = []cur = rootpre = 0         # 记录前一个节点的数值while cur or stack:if cur:                 # 右stack.append(cur)cur = cur.rightelse: cur = stack.pop()   # 中cur.val+= prepre = cur.valcur =cur.left       # 左return root

总结

二叉树这块的题目大部分可以通过递归和迭代两种方式来解决。
当遇到二叉搜索树时，可以利用其特性来简化代码。

对不同题目选择合适的遍历方式：

• 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。
• 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。
• 求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。

二叉树的遍历方式（递归和迭代）+层序遍历，必须要掌握。
要知道深度优先（前中后序遍历）和广度优先（层序遍历）对应哪些遍历方式。

关键是要掌握解决问题的方法，熟悉代码，理解题目。

二叉树的题就先做到这里，今天再看一下回溯算法的基础，明天开始做题。