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 node==None: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=[]node=rootwhile(node or stack):if node:res.append(node.val)if node.right:stack.append(node.right)node=node.leftelse:node=stack.pop()return res

1.2中序遍歷-左中右

遞歸的框架和先序遍歷一樣。

class Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""res=[]def dfs_inorder(node):if node==None: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=[]node=rootwhile(stack or node):if node:stack.append(node)node=node.leftelse:node=stack.pop()res.append(node.val)node=node.rightreturn res

1.3后序遍歷-左右中

遞歸的框架和先序，中序遍歷一致

class Solution(object):def postorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""res=[]def dfs_post(node):if node==None: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=[]node=rootwhile(stack or node):if node:res.append(node.val)if node.left:stack.append(node.left)node=node.rightelse:node=stack.pop()return res[::-1]

2.廣度優先遍歷bfs

層次遍歷，用隊列來幫助實現廣度優先遍歷

遞歸框架： 需要有一個level信息用于存儲該節點所處的層次。問題：在哪里新增res的層次呢–解決方案，先判斷l層次是否存在，不在的話新增。

class Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if root==None:return []res=[]def bfs(node,l):if node==None:returnif l>len(res)-1:res.append([])res[l].append(node.val)bfs(node.left,l+1)bfs(node.right,l+1)bfs(root,0)return res

迭代框架：隊列，先進先出，每層先統計隊列的長度，確認要彈出的元素個數。

class Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if root==None:return []que=[root]res=[]l=0while(que):n=len(que)res.append([])for i in range(n):node=que.pop(0)res[l].append(node.val)if node.left:que.append(node.left)if node.right:que.append(node.right)l+=1return res  

3.遍歷-常見問題

樹的問題，就是遍歷所有節點找出一個答案嘍。拿到問題，先考慮-深度優先？廣度優先；然后再考慮用遞歸？迭代。

3.1 二叉樹的最大深度

一道題帶你理解什么是自頂向上/自底向上–二叉樹的最大深度
給定一個二叉樹，找出其最大深度。二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

自頂向下

自頂向下 ：在每個遞歸層級上，先訪問節點來計算一些值，并在遞歸調用時將這些值傳遞給子節點。自頂向下的方案可以看作是一種先序遍歷

根節點的深度是1，對于一個節點其深度為x, 那么我們將知道其子節點的深度。在遞歸調用時自頂向下將節點的深度作為一個參數傳遞下去。每一個節點都知道自己的深度，對于葉子節點，可以通過比較確定需不需要更新更大的深度。

class Solution(object):def __init__(self):self.res=0def maxDepth(self, root):""":type root: TreeNode:rtype: int"""def dfs_top_down(node,l):if node==None:     # root 本身就是一個空指針returnif node.left==None and node.right==None:self.res=max(self.res,l)          # 用max 需要重新定義一個全局變量dfs_top_down(node.left,l+1)dfs_top_down(node.right,l+1)dfs_top_down(root,1)return self.res

自底向上

自底向上：在每個遞歸層級上，對所有的節點遞歸調用函數，然后根據返回值和根節點本身的值得到答案。自底向上的方案可以看作后序遍歷

如果知道一個根節點，以其左子節點為根的最大深度為l，以其右子節點為根的最大深度為如，那么這個根節點所在子樹的最大深度為$max(l,r)+1$（對于每個節點的答案，都可以在解決它的子節點問題的大難之后得到答案）

class Solution(object):def maxDepth(self, root):""":type root: TreeNode:rtype: int"""def dfs_bottom_up(node):if node==None:return 0left_l=dfs_bottom_up(node.left)right_l=dfs_bottom_up(node.right)return max(left_l,right_l)+1res=dfs_bottom_up(root)return res 

樹遞歸框架的小結：
自頂向上：需要使用一些參數和節點本身的值來決定傳遞給子節點參數
自底向上：如果知道子節點的答案就能知道該節點的答案，采用自底向上是個不錯的選擇

自底向上/自頂向上-都是深度優先遞歸，想要用深度優先迭代解需要將節點的層級狀態存下來。
如果使用廣度優先-無論是迭代，還是遞歸。res list 的層數就是最大深度。

3.2對稱二叉樹

給定一個二叉樹，檢查它是否為鏡像對稱。
解題關鍵：每次取到需要相互比較的兩個節點。

遞歸：所以兩個指針分別從根節點開始，一個往左子樹游走，一個往右子樹游走，依次查看鏡面對稱的節點是相等。也就是官方題解種所說的：驗證root 子樹和root子樹是不是鏡面對稱的。如果是的話，單獨的一棵root樹是鏡面對稱的。

class Solution(object):def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""def ismirror(node1,node2):if node1==None and node2==None:return Trueif node1==None or node2==None:return Falsereturn node1.val==node2.val and ismirror(node1.left,node2.right) and ismirror(node1.right,node2.left)flag=ismirror(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: bool"""que=[root,root]while(que):node1=que.pop(0)node2=que.pop(0)if node1==None and node2==None:continueif node1==None or node2==None:return Falseif node1.val!=node2.val:return Falseque.append(node1.left)que.append(node2.right)que.append(node1.right)que.append(node2.left)return True

3.3路徑總和

給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目標和。【深度優先】

遞歸：直覺上至頂向下，是可行的思路。在每個節點處將目標值-節點值，將這個差值傳給下一個節點，不斷重復，如果葉子節點處剛好減為0，說明存在一條路徑使得該路徑上所有節點的值相加等于目標和。遞歸函數應該返回True 或者False 程序實現上可以遍歷所有的路徑，將所有的結果取或，但是只有一個為True 其實遞歸就可以終止，這個該怎么寫。

class Solution(object):def hasPathSum(self, root, sum):""":type root: TreeNode:type sum: int:rtype: bool"""def has_top_down(node,target):if node==None:return Falseif node.left==None and node.right==None:if target-node.val==0: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: bool"""if root==None:return Falsestack=[(root,sum)]while(stack):node,target=stack.pop()if node.left==None and node.right==None and node.val-target==0:return Trueif node.left:stack.append((node.left,target-node.val))if node.right:stack.append((node.right,target-node.val))return False

4.重構-常見問題

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: TreeNode"""postorder_inver = postorder[::-1]def helper(left_idx=0, right_idx=len(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_idx=0, inorder_idx+1=1,# 左右節點調用都返回Noneinorder_idx = inorder.index(root_val)root.right = helper(inorder_idx+1, 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_idx=0, right_idx=len(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_idx+1, right_idx)return rootreturn helper()

4.3填充每個節點的下一個右側節點指針

填充一個完美二叉樹的每個解答的每個節點的下一個右側節點。完美二叉樹說的是，所有葉子節點都在同一層。

思路：關鍵找到每一個節點的下一個節點，那不就是二叉樹的層次遍歷。
每層的節點的next指針指其下一個節點，用l來控制該層的最后一個節點指向None。

class Solution(object):def connect(self, root):""":type root: Node:rtype: Node"""if 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)i+=1return root

4.4填充每個節點的下一個右側節點指針2

給定一個二叉樹，填充它每個next指針指向右側節點，同一層的最右側節點填充為None.
思路：不是一棵完美的二叉樹，不過還是樹的層次遍歷，上一題的框架依舊可以使用。
代碼只diff 了一行

"""
# Definition for a Node.
class Node(object):def __init__(self, val=0, left=None, right=None, next=None):self.val = valself.left = leftself.right = rightself.next = next
"""class Solution(object):def connect(self, root):""":type root: Node:rtype: Node"""if 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)i+=1return root

4.5二叉樹的最近公共祖先

給定一個二叉樹，找到該樹中兩個指定節點的最近公共祖先。
官方思路1:遞歸
遞歸遍歷整棵樹，定義$f_x$表示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 None

4.6二叉樹的序列化和反序列化

將二叉樹序列化為一個字符串，將得到的字符串反序列化為二叉樹。
說明：不要使用類成員/全局/靜態變量來存儲狀態，序列化和反序列化算法應該是無狀態的。–什么是無狀態？

序列化和反序列化遞歸順序一致就可以。

class Codec:def serialize(self, root):"""Encodes a tree to a single string.:type root: TreeNode:rtype: str"""def 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: TreeNode"""def 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 root==None:returnself.invertTree(root.left)self.invertTree(root.right)root.left,root.right=root.right,root.leftreturn root

迭代-自頂向下的交換過程

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.2合并兩棵二叉樹

leetcode617: 兩棵樹有公共結點處的值為兩數對應節點值想加

遞歸

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

迭代-首先把兩棵樹的根節點入棧，棧中的每個元素都會存放兩個根節點，并且棧頂的元素表示當前需要處理的節點。
以t1作為最后的輸出返回，
當前結點的處理（ 在stack里面的東西都是非空的）：
兩者相加的值放入t1.val
子結點的處理：
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