做教育的网站需要资质吗,广告优化师工作内容,网站建设介绍ppt,怎么搭建自己的博客代码随想录 - Day30 - 修剪二叉树#xff0c;转换二叉树 二叉树总结
669. 修剪二叉搜索树
有点像是删除二叉搜索树的变形#xff0c;改变了删除条件而已。 递归法#xff1a;
class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) - O…代码随想录 - 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 root108. 将有序数组转换为二叉搜索树
对于奇数长度的数组可以直接取中点对于偶数长度的数组则需要用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 root538. 把二叉搜索树转换为累加树
题目中的累加是右中左的顺序进行累加从最大的节点值累加到最小的节点值。 所以要反中序遍历该二叉树然后顺序累加。 需要一个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总结
二叉树这块的题目大部分可以通过递归和迭代两种方式来解决。 当遇到二叉搜索树时可以利用其特性来简化代码。
对不同题目选择合适的遍历方式
涉及到二叉树的构造无论普通二叉树还是二叉搜索树一定前序都是先构造中节点。求普通二叉树的属性一般是后序一般要通过递归函数的返回值做计算。求二叉搜索树的属性一定是中序了要不白瞎了有序性了。
二叉树的遍历方式递归和迭代层序遍历必须要掌握。 要知道深度优先前中后序遍历和广度优先层序遍历对应哪些遍历方式。
关键是要掌握解决问题的方法熟悉代码理解题目。
二叉树的题就先做到这里今天再看一下回溯算法的基础明天开始做题。
