网站开发者的设计构想,拓者设计吧注册码是永久的吗,西安seo网站关键词,做平面设计一般上哪个网站参考二叉树的遍历1.深度优先DFS1.1 DFS 递归解法1.1.1先序遍历1.1.2中序遍历1.1.3后序遍历1.2 DFS迭代解法1.2.1先序遍历1.2.2中序遍历1.2.3后序遍历2.广度优先BFS3.二叉树的最大深度3.1递归3.2迭代4.翻转二叉树4.1递归4.1迭代5.合并两棵二叉树5.1递归5.2迭代有两种通用的遍历树的策…
二叉树的遍历1.深度优先DFS1.1 DFS 递归解法1.1.1先序遍历1.1.2中序遍历1.1.3后序遍历1.2 DFS迭代解法1.2.1先序遍历1.2.2中序遍历1.2.3后序遍历2.广度优先BFS3.二叉树的最大深度3.1递归3.2迭代4.翻转二叉树4.1递归4.1迭代5.合并两棵二叉树5.1递归5.2迭代有两种通用的遍历树的策略深度优先遍历、广度优先遍历。树本身是一个递归的结构利用树类构造一个棵二叉树
class TreeNode(object):def __init__(self, x):self.val xself.left Noneself.right None
TTreeNode(1)
n1T.leftTreeNode(2)
n2T.rightTreeNode(3)
n3n1.leftTreeNode(4)
n4n1.rightTreeNode(5)1.深度优先DFS
DFSDepth First Search为二叉树的深度优先遍历方式深度优先从根节点开始往深处搜索至某个叶子节点依据左孩子右孩子根节点的相对遍历顺序可以分为先序遍历根-左-右中需遍历左-根-右后续遍历左-右-根。
1.1 DFS 递归解法
深度优先递归解法的三种顺序框架一致。递归最重要的一点递归结束条件1当前节点为空或者递归程序执行完最后一行。
1.1.1先序遍历
根-左-右 输出[1,2,4,8,9,5,3,6,7]
class Solution(object):def PreOrder_rec(self,root):res[]def DFS_pre(node,res):if nodeNone: returnres.append(node.val) # 先中DFS_pre(node.left,res) # 递归左子树DFS_pre(node.right,res) # 递归右子树DFS_pre(root,res)return res1.1.2中序遍历
左-根-右 输出[8,4,9,2,5,1,6,3,7]
class Solution(object):def InOrder_rec(self, root):res[]def DFS_In(node,res):if nodeNone:returnDFS_In(node.left,res)res.append(node.val)DFS_In(node.right,res)DFS_In(root,res)return res1.1.3后序遍历
左-右-根 输出[8,9,4,5,2,6,7,3,1]
class Solution(object):def BackOrder_rec(self, root):res[]def DFS_Back(node,res):if nodeNone:returnDFS_Back(node.left,res)DFS_Back(node.right,res)res.append(node.val)DFS_Back(root,res)return res1.2 DFS迭代解法
二叉树深度优先迭代 要借助栈先进后出的特点。依据三种不同的顺序将不同的节点压入堆栈。
1.2.1先序遍历
根-左-右 输出[1,2,4,8,9,5,3,6,7]。维护一个堆栈stackpython中可以用List 高效实现 从根结点开始currRoot; 如果当前节点非空 访问当前结点的值将当前节点的右子树节点推入堆栈更新当前结点currcurr.left.; 如果当前节点为空弹出堆栈保存的最后一个右子树结点。
class Solution(object):def PreOrder_iter(self, root)::type root: TreeNode:rtype: List[List[int]]res[]stack[]currrootwhile(curr or stack):if curr:res.append(curr.val)stack.append(curr.right) # 递归到叶子结点时会出现stack 增加None的情形currcurr.left # 将None pop 出来就是多了一次无增res操作else:currstack.pop()return res1.2.2中序遍历
左-根-右 输出[8,4,9,2,5,1,6,3,7] 维护一个堆栈stackpython中可以用List 高效实现。 从根结点开始currRoot 如果当前节点非空:将当前结点推入堆栈更新当前结点currcurr.left 如果当前节点为空弹出堆栈保存的最后一个结点访问该结点的值更新当前结点currcurr.right.
class Solution(object):def InOrer_iter(self, root)::type root: TreeNode:rtype: List[List[int]]res[]stack[]currrootwhile(curr or stack):if curr:stack.append(curr)currcurr.left # 一直搜索左子树到叶子节点,将路径上的结点推入堆栈else: currstack.pop()res.append(curr.val)currcurr.right # 访问右子树结点return res1.2.3后序遍历
左-右-根 输出[8,9,4,5,2,6,7,3,1] 维护一个堆栈stackpython中可以用List 高效实现。 从根结点开始currRoot 如果当前节点非空:将当前结点推入堆栈更新当前结点currcurr.left 如果当前节点为空弹出堆栈保存的最后一个结点访问该结点的值更新当前结点currcurr.right.
class Solution(object):def BackOrder_iter(self, root)::type root: TreeNode:rtype: List[List[int]]res[]stack[]currrootwhile(curr or stack): # 左右根尅分解为根右左逆序根右左和根左右是一样的实现框架if curr:res.append(curr.val)stack.append(curr.left)currcurr.rightelse:currstack.pop()return res[::-1]2.广度优先BFS
BFSBreadth First Search为二叉树的广度优先遍历方式又叫层次遍历从根节点开始逐层遍历二叉树。1-2-3-4-5-6-7-8-9
借助队列 先进后出 的特点将节点不断推入队列中。python 中用list可以快速实现队列。 迭代解法 输出[1,2,3,4,5,6,7,8,9]
class Solution(object):def BFS_iter1(self, root)::type root: TreeNode:rtype: List[List[int]]levels[]queue[root]if not root:return levelswhile(queue): # nodequeue.pop(0) levels.append(node.val)if node.left: # 装进队列里的元素都是非空的。queue.append(node.left)if node.right:queue.append(node.right)return levelsleetcode 102 要求输出的结果每一层的元素放在一起则需要维护一个list,用于放置每层的元素levels[[1],[2,3],[4,5,6,7],[8,9]],同时一个level变量用于指示当前节点位于的层数。
迭代解法 输出[[1],[2,3],[4,5,6,7],[8,9]]
class Solution(object):def levelOrder_iter2(self, root)::type root: TreeNode:rtype: List[List[int]]levels[]queue[root]if not root:return levelswhile(queue): # 处理每一层前增加一次levels装该层的节点值levels.append([])n_qlen(queue) # 该层节点个数for i in range(n_q): # i:[0,n_q-1] # 逐个处理该层节点首先弹出队列首记录数值有左右孩子的将孩子压入队列nodequeue.pop(0)levels[-1].append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return levels递归解法 输出[[1],[2,3],[4,5,6,7],[8,9]] 实际上是利用DFS实现的BFS每当DFS遍历到一个新的节点就把它加入到所在层的list里面去。
class Solution(object):def levelOrder_rec(self, root)::type root: TreeNode:rtype: List[List[int]]levels[]if not root:return levelsdef BFS_rec(node,level):if len(levels)level: # level作为levels 的索引应该len(levels),如果相等则需要增加levels的装载能力扩容levels.append([])levels[level].append(node.val) # 将当前节点放入指定的层if node.left: # 如果有左右孩子递归调用BFS_recBFS_rec(node.left,level1) if node.right:BFS_rec(node.right,level1)BFS_rec(root,0)return levels参考博文 二叉树的前中后遍历,层次遍历,树的递归问题递归与迭代pythonhttps://www.cnblogs.com/liuyicai/p/10156455.html 二叉树及其遍历方法—python实现https://www.cnblogs.com/lliuye/p/9143676.html
3.二叉树的最大深度
3.1递归
def Max_depth(node):if nodeNone:return 0dlDFS(node.left)drDFS(node.right)resmax(dl,dr)1return res
resMax_depth(root)
return res3.2迭代 def maxDepth(self, root):de0if root:stack[(1,root)]else:return 0while(stack):cur_de,nodestack.pop()if node: # 只有当结点存在时1后的深度才会被采用demax(de,cur_de)stack.append((cur_de1,node.left))stack.append((cur_de1,node.right))return de4.翻转二叉树
4.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 root4.1迭代
自顶向下的交换过程
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.合并两棵二叉树
leetcode617: 两棵树有公共结点处的值为两数对应节点值想加
5.1递归
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 t15.2迭代
首先把两棵树的根节点入栈栈中的每个元素都会存放两个根节点并且栈顶的元素表示当前需要处理的节点。 以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
