建立一个企业网站需要花多少钱,如何为网站开发app,网站布局结构主要分为,湖北分行建设银行网站leetcode-explore-learn-数据结构-二叉树10.概述1.深度优先遍历dfs1.1先序遍历-中左右1.2中序遍历-左中右1.3后序遍历-左右中2.广度优先遍历bfs3.遍历-常见问题3.1 二叉树的最大深度自顶向下自底向上3.2对称二叉树3.3路径总和4.重构-常见问题4.1根据中序和后序遍历序列构造二叉…
leetcode-explore-learn-数据结构-二叉树10.概述1.深度优先遍历dfs1.1先序遍历-中左右1.2中序遍历-左中右1.3后序遍历-左右中2.广度优先遍历bfs3.遍历-常见问题3.1 二叉树的最大深度自顶向下自底向上3.2对称二叉树3.3路径总和4.重构-常见问题4.1根据中序和后序遍历序列构造二叉树4.2根据前序和中序遍历序列构造二叉树4.3填充每个节点的下一个右侧节点指针4.4填充每个节点的下一个右侧节点指针24.5二叉树的最近公共祖先4.6二叉树的序列化和反序列化5.other5.1翻转二叉树5.2合并两棵二叉树note for :https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/7/0.概述
二叉树节点结构所有例题的编程语言为python
class TreeNode(object):def __init__(self, x):self.val xself.left Noneself.right None树结构本身是递归定义的一个节点包含一个值和一个指向其他节点的列表。树的定义天然带有递归的属性树的许多问题可以通过递归的方式来解决。对于每一个递归层级我们只需要关注单个节点内的问题然后通过递归调用来解决其子节点问题。
二叉树是一种典型的树状结构每个节点最多有两个子树的树通常被称作“左子树”和“右子树”。
二叉树用来存储具有树结构的数据我们通过访问树的各个结点来进行数据处理。可以逐层访问树节点【广度优先-Breadth First Search-BFS】又叫层次遍历。也可以逐条路径(每一个可能的分支路径深入到不能再深入为止)访问结点【深度优先-Depth First Search-DFS】。 其中 深度优先 按照根节点被访问到的顺序又可分为【先序遍历】、【中序遍历】、【后序遍历】。
广度优先/深度优先 遍历都各自拥有【迭代】和【递归】两种代码实现方式。 迭代找一种容器【队列/堆栈】存放暂时未访问到的节点等到访问它了再把它弹出来。迭代退出条件是容器是空的即没有未被访问过的结点即所有节点都被访问过了。 递归需要存在递归函数和原函数原函数中开启递归入口递归函数不断递归求解。递归退出条件-如果节点为空无需再往下递归。
二叉树常见的问题遍历二叉树能够做啥 二叉树的最大深度理解【自顶向上】、【自底向上】递归的经典例子。 对称二叉树 路径综总和
1.深度优先遍历dfs
深度优先 按照根节点被访问到的顺序可分为【先序遍历】、【中序遍历】、【后序遍历】。
1.1先序遍历-中左右
递归的框架有了如何在res list中加入答案在内层再定义一个函数
class Solution(object):def preorderTraversal(self, root)::type root: TreeNode:rtype: List[int]res[]def dfs_pre(node):if nodeNone:returnres.append(node.val)dfs_pre(node.left)dfs_pre(node.right)dfs_pre(root)return res迭代的框架当前节点的右子树放入堆栈存起来。将当前节点的值放入res当前节点更新为当前节点的左子树节点。
class Solution(object):def preorderTraversal(self, root)::type root: TreeNode:rtype: List[int]stack[]res[]noderootwhile(node or stack):if node:res.append(node.val)if node.right:stack.append(node.right)nodenode.leftelse:nodestack.pop()return res1.2中序遍历-左中右
递归的框架和先序遍历一样。
class Solution(object):def inorderTraversal(self, root)::type root: TreeNode:rtype: List[int]res[]def dfs_inorder(node):if nodeNone:returndfs_inorder(node.left)res.append(node.val)dfs_inorder(node.right)dfs_inorder(root)return res迭代框架需要将什么放stack中呢根节点一路向左遍历到底部。将根节点都放进去放进去的就是有的节点。遍历到底端之后逐个弹出然后去该节点的右子树如果右子树为空就会弹该节点的父亲节点如果右子树不为空就可以迭代进去处理右子树。
class Solution(object):def inorderTraversal(self, root)::type root: TreeNode:rtype: List[int]stack[]res[]noderootwhile(stack or node):if node:stack.append(node)nodenode.leftelse:nodestack.pop()res.append(node.val)nodenode.rightreturn res1.3后序遍历-左右中
递归的框架和先序中序遍历一致
class Solution(object):def postorderTraversal(self, root)::type root: TreeNode:rtype: List[int]res[]def dfs_post(node):if nodeNone:returndfs_post(node.left)dfs_post(node.right)res.append(node.val)dfs_post(root)return res迭代的框架中右左的逆序就是左右中。在伪前序遍历保存左节点的结果下逆序输出即可。
class Solution(object):def postorderTraversal(self, root)::type root: TreeNode:rtype: List[int]stack[]res[]noderootwhile(stack or node):if node:res.append(node.val)if node.left:stack.append(node.left)nodenode.rightelse:nodestack.pop()return res[::-1]2.广度优先遍历bfs
层次遍历用队列来帮助实现广度优先遍历
递归框架 需要有一个level信息用于存储该节点所处的层次。问题在哪里新增res的层次呢–解决方案先判断l层次是否存在不在的话新增。
class Solution(object):def levelOrder(self, root)::type root: TreeNode:rtype: List[List[int]]if rootNone:return []res[]def bfs(node,l):if nodeNone:returnif llen(res)-1:res.append([])res[l].append(node.val)bfs(node.left,l1)bfs(node.right,l1)bfs(root,0)return res
迭代框架队列先进先出每层先统计队列的长度确认要弹出的元素个数。
class Solution(object):def levelOrder(self, root)::type root: TreeNode:rtype: List[List[int]]if rootNone:return []que[root]res[]l0while(que):nlen(que)res.append([])for i in range(n):nodeque.pop(0)res[l].append(node.val)if node.left:que.append(node.left)if node.right:que.append(node.right)l1return res 3.遍历-常见问题
树的问题就是遍历所有节点找出一个答案喽。拿到问题先考虑-深度优先广度优先然后再考虑用递归迭代。
3.1 二叉树的最大深度
一道题带你理解什么是自顶向上/自底向上–二叉树的最大深度 给定一个二叉树找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
自顶向下
自顶向下 在每个递归层级上先访问节点来计算一些值并在递归调用时将这些值传递给子节点。自顶向下的方案可以看作是一种先序遍历
根节点的深度是1对于一个节点其深度为x, 那么我们将知道其子节点的深度。在递归调用时自顶向下将节点的深度作为一个参数传递下去。每一个节点都知道自己的深度对于叶子节点可以通过比较确定需不需要更新更大的深度。
class Solution(object):def __init__(self):self.res0def maxDepth(self, root)::type root: TreeNode:rtype: intdef dfs_top_down(node,l):if nodeNone: # root 本身就是一个空指针returnif node.leftNone and node.rightNone:self.resmax(self.res,l) # 用max 需要重新定义一个全局变量dfs_top_down(node.left,l1)dfs_top_down(node.right,l1)dfs_top_down(root,1)return self.res自底向上
自底向上在每个递归层级上对所有的节点递归调用函数然后根据返回值和根节点本身的值得到答案。自底向上的方案可以看作后序遍历
如果知道一个根节点以其左子节点为根的最大深度为l以其右子节点为根的最大深度为如那么这个根节点所在子树的最大深度为max(l,r)1max(l,r)1max(l,r)1对于每个节点的答案都可以在解决它的子节点问题的大难之后得到答案
class Solution(object):def maxDepth(self, root)::type root: TreeNode:rtype: intdef dfs_bottom_up(node):if nodeNone:return 0left_ldfs_bottom_up(node.left)right_ldfs_bottom_up(node.right)return max(left_l,right_l)1resdfs_bottom_up(root)return res 树递归框架的小结 自顶向上需要使用一些参数和节点本身的值来决定传递给子节点参数 自底向上如果知道子节点的答案就能知道该节点的答案采用自底向上是个不错的选择
自底向上/自顶向上-都是深度优先递归想要用深度优先迭代解需要将节点的层级状态存下来。 如果使用广度优先-无论是迭代还是递归。res list 的层数就是最大深度。
3.2对称二叉树
给定一个二叉树检查它是否为镜像对称。 解题关键每次取到需要相互比较的两个节点。 递归所以两个指针分别从根节点开始一个往左子树游走一个往右子树游走依次查看镜面对称的节点是相等。也就是官方题解种所说的验证root 子树和root子树是不是镜面对称的。如果是的话单独的一棵root树是镜面对称的。
class Solution(object):def isSymmetric(self, root)::type root: TreeNode:rtype: booldef ismirror(node1,node2):if node1None and node2None:return Trueif node1None or node2None:return Falsereturn node1.valnode2.val and ismirror(node1.left,node2.right) and ismirror(node1.right,node2.left)flagismirror(root,root) # root 和root为镜像root自己本身为镜像return flag迭代队列初始化为[root,root]将需要比较的点放在相邻位置。每次弹出两个节点如果两个节点相同时node1.left 和node2.right 放入队列将node1.right与node2.left放入队列。这样押入弹出直至对比完该对比的节点。
class Solution(object):def isSymmetric(self, root)::type root: TreeNode:rtype: boolque[root,root]while(que):node1que.pop(0)node2que.pop(0)if node1None and node2None:continueif node1None or node2None:return Falseif node1.val!node2.val:return Falseque.append(node1.left)que.append(node2.right)que.append(node1.right)que.append(node2.left)return True3.3路径总和
给定一个二叉树和一个目标和判断该树中是否存在根节点到叶子节点的路径这条路径上所有节点值相加等于目标和。【深度优先】
递归直觉上至顶向下是可行的思路。在每个节点处将目标值-节点值将这个差值传给下一个节点不断重复如果叶子节点处刚好减为0说明存在一条路径使得该路径上所有节点的值相加等于目标和。递归函数应该返回True 或者False 程序实现上可以遍历所有的路径将所有的结果取或但是只有一个为True 其实递归就可以终止这个该怎么写。 class Solution(object):def hasPathSum(self, root, sum)::type root: TreeNode:type sum: int:rtype: booldef has_top_down(node,target):if nodeNone:return Falseif node.leftNone and node.rightNone:if target-node.val0:return Trueif has_top_down(node.left,target-node.val):return Trueif has_top_down(node.right,target-node.val):return Truereturn Falsereturn has_top_down(root,sum)迭代维护一个堆栈用于储存每一个节点和其需要匹配的信息。每次从堆栈中弹出一个节点判断该节点是否为叶子节点如果为叶子节点则判断对应的目标值-节点值是否为0如果该节点不为叶子节点将其子节点和相应的信息押入堆栈中。–堆栈如此维护深度优先遍历的结构遍历完一条路径之后再去遍历其他的路径。第一条走过的是最右边的路径是一个由右往左扫描的过程。
class Solution(object):def hasPathSum(self, root, sum)::type root: TreeNode:type sum: int:rtype: boolif rootNone:return Falsestack[(root,sum)]while(stack):node,targetstack.pop()if node.leftNone and node.rightNone and node.val-target0:return Trueif node.left:stack.append((node.left,target-node.val))if node.right:stack.append((node.right,target-node.val))return False4.重构-常见问题
4.1根据中序和后序遍历序列构造二叉树
inorder[9,3,15,20,7] 左根右 postorder[9,15,7,20,3] 左右根逆序就是根右左[3,20,7,15,9] 由后序遍历中可知根节点是3在中序遍历中可以确定左右子树序列是多少。如何提取下一个根节点呢取根和左右子树递归构造该如何衔接。 inorder 用来控制递归出口 postorder 才是提供根节点的源泉。
class Solution(object):def __init__(self):self.root_idx 0def buildTree(self, inorder, postorder)::type inorder: List[int]:type postorder: List[int]:rtype: TreeNodepostorder_inver postorder[::-1]def helper(left_idx0, right_idxlen(postorder)):if left_idx right_idx:return Noneroot_val postorder_inver[self.root_idx]self.root_idx 1root TreeNode(root_val)# 只有一个节点时[a] inorder_idx 0, left_idx0, inorder_idx11,# 左右节点调用都返回Noneinorder_idx inorder.index(root_val)root.right helper(inorder_idx1, right_idx)root.left helper(left_idx, inorder_idx)return rootreturn helper()4.2根据前序和中序遍历序列构造二叉树
preorder[3,9,20,15,7] 中左右 inorder[9,3,15,20,7] 左中右 一个根节点可以将中序遍历划分为左一半右一半。 全局变量pre_idx每次运行一次helper函数一次加1取下一根节点直至左子树运行完对应的根节点下标也应该遍历完全了。 剩余问题index不因该是根节点的在中序遍历中的下标么左子树包含的内容不是应该为[0,index-1] 根递归出口有关不是直接索引元素。
class Solution(object):def __init__(self):self._root_idx 0def buildTree(self, preorder, inorder)::type preorder: List[int]:type inorder: List[int]:rtype: TreeNode# 前序-中左右 中序-左右中def helper(left_idx0, right_idxlen(inorder)):if left_idx right_idx:return Noneroot_val preorder[self._root_idx]self._root_idx 1root TreeNode(root_val)inorder_idx inorder.index(root_val)root.left helper(left_idx, inorder_idx)root.right helper(inorder_idx1, right_idx)return rootreturn helper()4.3填充每个节点的下一个右侧节点指针
填充一个完美二叉树的每个解答的每个节点的下一个右侧节点。完美二叉树说的是所有叶子节点都在同一层。
思路关键找到每一个节点的下一个节点那不就是二叉树的层次遍历。 每层的节点的next指针指其下一个节点用l来控制该层的最后一个节点指向None。
class Solution(object):def connect(self, root)::type root: Node:rtype: Nodeif root None:return rootnode_que [root]while(node_que):level_node_num len(node_que)i 0while(node_que and i level_node_num):node node_que.pop(0)if i level_node_num - 1:node.next node_que[0]if node.left: # 左右节点同时存在所以只需要判断一个非空即可node_que.append(node.left)node_que.append(node.right)i1return root4.4填充每个节点的下一个右侧节点指针2
给定一个二叉树填充它每个next指针指向右侧节点同一层的最右侧节点填充为None. 思路不是一棵完美的二叉树不过还是树的层次遍历上一题的框架依旧可以使用。 代码只diff 了一行 # Definition for a Node.
class Node(object):def __init__(self, val0, leftNone, rightNone, nextNone):self.val valself.left leftself.right rightself.next next
class Solution(object):def connect(self, root)::type root: Node:rtype: Nodeif root None:return rootnode_que [root]while(node_que):level_node_num len(node_que)i 0while(node_que and i level_node_num):node node_que.pop(0)if i level_node_num - 1:node.next node_que[0]if node.left:node_que.append(node.left)if node.right: // 与4.4diff行node_que.append(node.right)i1return root4.5二叉树的最近公共祖先
给定一个二叉树找到该树中两个指定节点的最近公共祖先。 官方思路1:递归 递归遍历整棵树定义fxf_xfx表示x节点的子树中是否包含p节点或者q节点如果包含则为true.采用自底向上从叶子节点开始更新保证满足条件的公共祖先深度最深。
class Solution(object):def __init__(self):self.ans Nonedef lowestCommonAncestor(self, root, p, q):def bottom_up(node):if node None:return Falseleft_mark bottom_up(node.left) # 左右子树中是否包含pq节点right_mark bottom_up(node.right)current_mark (node.val p.val) or (node.val q.val)# print(node.val, left_mark, right_mark, current_mark)if (current_mark left_mark right_mark 2):self.ans nodereturn Truereturn current_mark or right_mark or left_markbottom_up(root)return self.ans官方思路2:储存父节点 用hash表存储所有节点的父亲节点然后利用节点的父亲节点的信息从p往上跳直至根节点记录已经访问过的节点再从q节点开始不断往上跳每次上跳一个节点就去p已访问的节点中寻找是否已经访问过该节点。第一次遇到的p已经访问的节点则该节点为答案。 难点1父亲节点hash表。{child1:root1,child2:root1},只要遍历过二叉树的所有节点就可以实现这个。 难点2:从p开始不断在父亲hash表中找父亲节点直至找不到父亲节点的跟节点将所有路径放入[]中。 技巧还是将节点放进去。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def __init__(self):self.father_hash {}self.vist_hash {}def lowestCommonAncestor(self, root, p, q):def dfs_contruct_father_hash(node):if node None:return if node.left:self.father_hash[node.left] nodeif node.right:self.father_hash[node.right] nodedfs_contruct_father_hash(node.left)dfs_contruct_father_hash(node.right)self.father_hash[root] Nonedfs_contruct_father_hash(root)node pwhile(p):self.vist_hash[p] Truep self.father_hash[p]node qwhile(q):if self.vist_hash.get(q):return qq self.father_hash[q]return None4.6二叉树的序列化和反序列化
将二叉树序列化为一个字符串将得到的字符串反序列化为二叉树。 说明不要使用类成员/全局/静态变量来存储状态序列化和反序列化算法应该是无状态的。–什么是无状态
序列化和反序列化递归顺序一致就可以。
class Codec:def serialize(self, root):Encodes a tree to a single string.:type root: TreeNode:rtype: strdef dfs_serialize(node, iter_str):if node None:iter_str None,return iter_striter_str {0},.format(node.val)iter_str dfs_serialize(node.left, iter_str)iter_str dfs_serialize(node.right, iter_str)return iter_strreturn dfs_serialize(root, )def deserialize(self, data):Decodes your encoded data to tree.:type data: str:rtype: TreeNodedef dfs_deserialize(data_list):# print(data_list)if data_list[0] None:data_list.pop(0)return Nonenode TreeNode(int(data_list[0]))data_list.pop(0)node.left dfs_deserialize(data_list)node.right dfs_deserialize(data_list)return nodedata_list data.split(,)return dfs_deserialize(data_list)5.other
5.1翻转二叉树
递归-自低向上的交换过程
class Solution(object):def invertTree(self, root):if rootNone:returnself.invertTree(root.left)self.invertTree(root.right)root.left,root.rightroot.right,root.leftreturn root迭代-自顶向下的交换过程
class Solution(object):def invertTree(self, root)::type root: TreeNode:rtype: TreeNodeif root:q[root]else:return rootwhile(q):currq.pop(0)curr.left,curr.rightcurr.right,curr.leftif curr.left:q.append(curr.left)if curr.right:q.append(curr.right)return root5.2合并两棵二叉树
leetcode617: 两棵树有公共结点处的值为两数对应节点值想加
递归
class Solution(object):def mergeTrees(self, t1, t2):if not t1 and not t2:return NonerootTreeNode(0)if t1 and t2:root.valt1.valt2.valroot.leftself.mergeTrees(t1.left,t2.left)root.rightself.mergeTrees(t1.right,t2.right)elif t1:root.valt1.valroot.leftself.mergeTrees(t1.left,None)root.rightself.mergeTrees(t1.right,None)else:root.valt2.valroot.leftself.mergeTrees(None,t2.left)root.rightself.mergeTrees(None,t2.right)return rootclass Solution(object):def mergeTrees2(self, t1, t2):if t1None:return t2if t2None:return t1t1.valt2.valt1.leftself.mergeTrees2(t1.left,t2.left)t1.rightself.mergeTrees2(t1.right,t2.right)return t1迭代-首先把两棵树的根节点入栈栈中的每个元素都会存放两个根节点并且栈顶的元素表示当前需要处理的节点。 以t1作为最后的输出返回 当前结点的处理 在stack里面的东西都是非空的 两者相加的值放入t1.val 子结点的处理 t1没有做孩子t2的左孩子给t1. t1,t2同时有左孩子将其同时入栈 右孩子的处理同理。
class Solution(object):def mergeTrees(self, t1, t2):if t1None:return t2if t2None:return t1stack[(t1,t2)]while(stack):node1,node2stack.pop() # 在stack里面的东西都是非零的node1.valnode2.valif node1.leftNone:node1.leftnode2.leftelif node1.left and node2.left: # 1.left 和2.left同时非零stack.append([node1.left,node2.left])if node1.rightNone:node1.rightnode2.right # 放过来之后就有。elif node1.right and node2.right: # 1.left 和2.left同时非零stack.append([node1.right,node2.right])return t1
