二叉樹的遍歷

• 1.深度優(yōu)先DFS
• • 1.1 DFS 遞歸解法
  • • 1.1.1先序遍歷
    • 1.1.2中序遍歷
    • 1.1.3后序遍歷
  • 1.2 DFS迭代解法
  • • 1.2.1先序遍歷
    • 1.2.2中序遍歷
    • 1.2.3后序遍歷
• 2.廣度優(yōu)先BFS
• 3.二叉樹的最大深度
• • 3.1遞歸
  • 3.2迭代
• 4.翻轉(zhuǎn)二叉樹
• • 4.1遞歸
  • 4.1迭代
• 5.合并兩棵二叉樹
• • 5.1遞歸
  • 5.2迭代

有兩種通用的遍歷樹的策略：深度優(yōu)先遍歷、廣度優(yōu)先遍歷。
（樹本身是一個遞歸的結(jié)構(gòu)）

利用樹類構(gòu)造一個棵二叉樹：

class TreeNode(object):def __init__(self, x):self.val = xself.left = Noneself.right = None T=TreeNode(1) n1=T.left=TreeNode(2) n2=T.right=TreeNode(3) n3=n1.left=TreeNode(4) n4=n1.right=TreeNode(5)

1.深度優(yōu)先DFS

DFS（Depth First Search）為二叉樹的深度優(yōu)先遍歷方式，深度優(yōu)先從根節(jié)點(diǎn)開始，往深處搜索至某個葉子節(jié)點(diǎn)，依據(jù)左孩子，右孩子，根節(jié)點(diǎn)的相對遍歷順序，可以分為先序遍歷（根-左-右），中需遍歷（左-根-右），后續(xù)遍歷（左-右-根）。

1.1 DFS 遞歸解法

深度優(yōu)先遞歸解法的三種順序，框架一致。遞歸最重要的一點(diǎn)：遞歸結(jié)束條件，（1）當(dāng)前節(jié)點(diǎn)為空，或者遞歸程序執(zhí)行完最后一行。

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 node==None: returnres.append(node.val) # 先中DFS_pre(node.left,res) # 遞歸左子樹DFS_pre(node.right,res) # 遞歸右子樹DFS_pre(root,res)return res

1.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 node==None:returnDFS_In(node.left,res)res.append(node.val)DFS_In(node.right,res)DFS_In(root,res)return res

1.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 node==None:returnDFS_Back(node.left,res)DFS_Back(node.right,res)res.append(node.val)DFS_Back(root,res)return res

1.2 DFS迭代解法

二叉樹深度優(yōu)先迭代 要借助棧（先進(jìn)后出）的特點(diǎn)。依據(jù)三種不同的順序?qū)⒉煌墓?jié)點(diǎn)壓入堆棧。

1.2.1先序遍歷

根-左-右 輸出：[1,2,4,8,9,5,3,6,7]。維護(hù)一個堆棧stack（python中可以用List 高效實(shí)現(xiàn)）
從根結(jié)點(diǎn)開始（curr=Root）;
如果當(dāng)前節(jié)點(diǎn)非空 訪問當(dāng)前結(jié)點(diǎn)的值，將當(dāng)前節(jié)點(diǎn)的右子樹節(jié)點(diǎn)推入堆棧，更新當(dāng)前結(jié)點(diǎn)：curr=curr.left.;
如果當(dāng)前節(jié)點(diǎn)為空：彈出堆棧保存的最后一個右子樹結(jié)點(diǎn)。

class Solution(object):def PreOrder_iter(self, root):""":type root: TreeNode:rtype: List[List[int]]"""res=[]stack=[]curr=rootwhile(curr or stack):if curr:res.append(curr.val)stack.append(curr.right) # 遞歸到葉子結(jié)點(diǎn)時，會出現(xiàn)stack 增加None的情形curr=curr.left # 將None pop 出來就是多了一次無增res操作else:curr=stack.pop()return res

1.2.2中序遍歷

左-根-右 輸出：[8,4,9,2,5,1,6,3,7]
維護(hù)一個堆棧stack（python中可以用List 高效實(shí)現(xiàn)）。
從根結(jié)點(diǎn)開始（curr=Root）：
如果當(dāng)前節(jié)點(diǎn)非空:將當(dāng)前結(jié)點(diǎn)推入堆棧，更新當(dāng)前結(jié)點(diǎn)：curr=curr.left；
如果當(dāng)前節(jié)點(diǎn)為空：彈出堆棧保存的最后一個結(jié)點(diǎn)，訪問該結(jié)點(diǎn)的值，更新當(dāng)前結(jié)點(diǎn)：curr=curr.right.

class Solution(object):def InOrer_iter(self, root):""":type root: TreeNode:rtype: List[List[int]]"""res=[]stack=[]curr=rootwhile(curr or stack):if curr:stack.append(curr)curr=curr.left # 一直搜索左子樹到葉子節(jié)點(diǎn),將路徑上的結(jié)點(diǎn)推入堆棧else: curr=stack.pop()res.append(curr.val)curr=curr.right # 訪問右子樹結(jié)點(diǎn)return res

1.2.3后序遍歷

左-右-根 輸出[8,9,4,5,2,6,7,3,1]
維護(hù)一個堆棧stack（python中可以用List 高效實(shí)現(xiàn)）。
從根結(jié)點(diǎn)開始（curr=Root）：
如果當(dāng)前節(jié)點(diǎn)非空:將當(dāng)前結(jié)點(diǎn)推入堆棧，更新當(dāng)前結(jié)點(diǎn)：curr=curr.left；
如果當(dāng)前節(jié)點(diǎn)為空：彈出堆棧保存的最后一個結(jié)點(diǎn)，訪問該結(jié)點(diǎn)的值，更新當(dāng)前結(jié)點(diǎn)：curr=curr.right.

class Solution(object):def BackOrder_iter(self, root):""":type root: TreeNode:rtype: List[List[int]]"""res=[]stack=[]curr=rootwhile(curr or stack): # 左右根尅分解為：根右左+逆序（根右左和根左右是一樣的實(shí)現(xiàn)框架）if curr:res.append(curr.val)stack.append(curr.left)curr=curr.rightelse:curr=stack.pop()return res[::-1]

2.廣度優(yōu)先BFS

BFS（Breadth First Search）為二叉樹的廣度優(yōu)先遍歷方式，又叫層次遍歷從根節(jié)點(diǎn)開始逐層遍歷二叉樹。1->2->3->4->5->6->7->8->9

借助隊列 先進(jìn)后出 的特點(diǎn)，將節(jié)點(diǎn)不斷推入隊列中。python 中用list可以快速實(shí)現(xiàn)隊列。
迭代解法 輸出[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): # node=queue.pop(0) levels.append(node.val)if node.left: # 裝進(jìn)隊列里的元素都是非空的。queue.append(node.left)if node.right:queue.append(node.right)return levels

---

leetcode 102 要求輸出的結(jié)果每一層的元素放在一起，則需要維護(hù)一個list,用于放置每層的元素，levels=[[1],[2,3],[4,5,6,7],[8,9]],同時一個level變量用于指示當(dāng)前節(jié)點(diǎn)位于的層數(shù)。

迭代解法 ：輸出[[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，裝該層的節(jié)點(diǎn)值levels.append([])n_q=len(queue) # 該層節(jié)點(diǎn)個數(shù)for i in range(n_q): # i:[0,n_q-1] # 逐個處理該層節(jié)點(diǎn)：首先彈出隊列首，記錄數(shù)值，有左右孩子的將孩子壓入隊列node=queue.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]]
實(shí)際上是利用DFS實(shí)現(xiàn)的BFS，每當(dāng)DFS遍歷到一個新的節(jié)點(diǎn)，就把它加入到所在層的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 的索引，應(yīng)該<len(levels),如果相等，則需要增加levels的裝載能力，擴(kuò)容levels.append([])levels[level].append(node.val) # 將當(dāng)前節(jié)點(diǎn)放入指定的層if node.left: # 如果有左右孩子，遞歸調(diào)用BFS_recBFS_rec(node.left,level+1) if node.right:BFS_rec(node.right,level+1)BFS_rec(root,0)return levels

參考博文：
二叉樹的前中后遍歷,層次遍歷,樹的遞歸問題（遞歸與迭代python）：https://www.cnblogs.com/liuyicai/p/10156455.html
二叉樹及其遍歷方法—python實(shí)現(xiàn)：https://www.cnblogs.com/lliuye/p/9143676.html

3.二叉樹的最大深度

3.1遞歸

def Max_depth(node):if node==None:return 0dl=DFS(node.left)dr=DFS(node.right)res=max(dl,dr)+1return res res=Max_depth(root) return res

3.2迭代

def maxDepth(self, root):de=0if root:stack=[(1,root)]else:return 0while(stack):cur_de,node=stack.pop()if node: # 只有當(dāng)結(jié)點(diǎn)存在時+1后的深度才會被采用de=max(de,cur_de)stack.append((cur_de+1,node.left))stack.append((cur_de+1,node.right))return de

4.翻轉(zhuǎn)二叉樹

4.1遞歸

自低向上的交換過程

class Solution(object):def invertTree(self, root):if root==None:returnself.invertTree(root.left)self.invertTree(root.right)root.left,root.right=root.right,root.leftreturn root

4.1迭代

自頂向下的交換過程

class Solution(object):def invertTree(self, root):""":type root: TreeNode:rtype: TreeNode"""if root:q=[root]else:return rootwhile(q):curr=q.pop(0)curr.left,curr.right=curr.right,curr.leftif curr.left:q.append(curr.left)if curr.right:q.append(curr.right)return root

5.合并兩棵二叉樹

leetcode617: 兩棵樹有公共結(jié)點(diǎn)處的值為兩數(shù)對應(yīng)節(jié)點(diǎn)值想加

5.1遞歸

class Solution(object):def mergeTrees(self, t1, t2):if not t1 and not t2:return Noneroot=TreeNode(0)if t1 and t2:root.val=t1.val+t2.valroot.left=self.mergeTrees(t1.left,t2.left)root.right=self.mergeTrees(t1.right,t2.right)elif t1:root.val=t1.valroot.left=self.mergeTrees(t1.left,None)root.right=self.mergeTrees(t1.right,None)else:root.val=t2.valroot.left=self.mergeTrees(None,t2.left)root.right=self.mergeTrees(None,t2.right)return rootclass Solution(object):def mergeTrees2(self, t1, t2):if t1==None:return t2if t2==None:return t1t1.val+=t2.valt1.left=self.mergeTrees2(t1.left,t2.left)t1.right=self.mergeTrees2(t1.right,t2.right)return t1

5.2迭代

首先把兩棵樹的根節(jié)點(diǎn)入棧，棧中的每個元素都會存放兩個根節(jié)點(diǎn)，并且棧頂?shù)脑乇硎井?dāng)前需要處理的節(jié)點(diǎn)。
以t1作為最后的輸出返回，
當(dāng)前結(jié)點(diǎn)的處理（ 在stack里面的東西都是非空的）：
兩者相加的值放入t1.val
子結(jié)點(diǎn)的處理：
t1沒有做孩子，t2的左孩子給t1.
t1,t2同時有左孩子，將其同時入棧，
右孩子的處理同理。

class Solution(object):def mergeTrees(self, t1, t2):if t1==None:return t2if t2==None:return t1stack=[(t1,t2)]while(stack):node1,node2=stack.pop() # 在stack里面的東西都是非零的node1.val+=node2.valif node1.left==None:node1.left=node2.leftelif node1.left and node2.left: # 1.left 和2.left同時非零stack.append([node1.left,node2.left])if node1.right==None:node1.right=node2.right # 放過來之后就有。elif node1.right and node2.right: # 1.left 和2.left同時非零stack.append([node1.right,node2.right])return t1

總結(jié)

以上是生活随笔為你收集整理的算法(2)-二叉树的遍历（递归/迭代）python实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。