題目
重建二叉樹
樹的子結構
二叉樹的鏡像
從上往下打印二叉樹（層序遍歷）
把二叉樹打印成多行
按之字形順序打印二叉樹
二叉搜索樹的第k個結點（中序遍歷）
二叉搜索樹的后序遍歷序列（后序遍歷）
二叉樹中和為某一值的路徑
二叉樹的深度
平衡二叉樹
二叉樹的下一個結點
對稱的二叉樹
序列化二叉樹
代碼實現
重建二叉樹
題目描述：輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。
思路：前序遍歷的第一個結點是根節點，據此和中序遍歷序列可以找到根節點的左子樹、右子樹包含的結點，返回的結果是樹的層序遍歷的結果{1,2,3,4,5,6,7,8}。典型題目，注意迭代的pre和tin的取值范圍。
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = None
class Solution:# 返回構造的TreeNode根節點def reConstructBinaryTree(self, pre, tin):# write code hereif len(pre)==0:return Noneroot=TreeNode(pre[0])TinIndex=tin.index(pre[0])root.left=self.reConstructBinaryTree(pre[1:TinIndex+1], tin[0:TinIndex])root.right=self.reConstructBinaryTree(pre[TinIndex+1:], tin[TinIndex+1:])return root樹的子結構
題目描述：輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）
思路：依次判斷A與B的left、right，判斷pRoot2是否是pRoot1的子結構。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:def HasSubtree(self, pRoot1, pRoot2):# write code here#這里認為pRoot1和pRoot2都為空時，沒法判斷子結構結果，認為比較的結果是False#if not pRoot1 and not pRoot2:# return Trueif not pRoot1 or not pRoot2:return Falsereturn self.is_subtree(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)def is_subtree(self, A, B):if not B:return Trueif not A or A.val != B.val:return Falsereturn self.is_subtree(A.left,B.left) and self.is_subtree(A.right, B.right)二叉樹的鏡像
題目描述：操作給定的二叉樹，將其變換為源二叉樹的鏡像。
思路：二叉樹每一層的結點進行左右交換，看得到的二叉樹的結點數值是否一致。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:def Mirror(self, root):# write code hereif not root:return None left, right = root.left, root.rightroot.left = rightroot.right = leftself.Mirror(root.left)self.Mirror(root.right)return root從上往下打印二叉樹（層序遍歷）
題目描述：從上往下打印出二叉樹的每個節點，同層節點從左至右打印。
思路：從左至右添加每一層的結點。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:# 返回從上到下每個節點值列表def PrintFromTopToBottom(self, root):# write code hereret = [] if root == None:return retbfs = [root]while(bfs):tbfs = []for node in bfs:ret.append(node.val)if node.left:tbfs.append(node.left)if node.right:tbfs.append(node.right)bfs = tbfsreturn ret把二叉樹打印成多行
題目描述：從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。
思路：注意和第13題的區別：這里是每一層輸出一行（用列表表示）。因而，輸出是一個嵌套列表。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:def Print(self, pRoot):if not pRoot:return []nodeStack=[pRoot]result=[]while nodeStack:res = []nextStack=[]for i in nodeStack:res.append(i.val)if i.left:nextStack.append(i.left)if i.right:nextStack.append(i.right)nodeStack=nextStackresult.append(res)return result按之字形順序打印二叉樹
題目描述：請實現一個函數按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。
思路：和第5題類似，但是這里需要對列表中的元素的位置序號進行“奇偶判斷”。注意：enumerate()結果的序號是從0開始的。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:def Print(self, pRoot):if not pRoot:return []nodeStack=[pRoot]result=[]while nodeStack:res = []nextStack=[]for i in nodeStack:res.append(i.val)if i.left:nextStack.append(i.left)if i.right:nextStack.append(i.right)nodeStack=nextStackresult.append(res)returnResult=[]#上述代碼的運行結果是[[z1],[z2],...,[zn]]，z1...zn表示對應的每一層的結點的值for i,v in enumerate(result):if i%2==0:returnResult.append(v)else:returnResult.append(v[::-1])return returnResult二叉搜索樹的第k個結點（中序遍歷）
題目描述：給定一棵二叉搜索樹，請找出其中的第k小的結點。例如，（5，3，7，2，4，6，8）中，按結點數值大小順序第三小結點的值為4。
思路：利用中序遍歷實現。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:# 中序遍歷找到第k個結點的數值def KthNode(self, pRoot, k):# write code hereif not pRoot: return Nonestack = []while pRoot or stack:while pRoot:stack.append(pRoot)pRoot = pRoot.leftpRoot = stack.pop()k -= 1if k == 0:return pRootpRoot = pRoot.right二叉搜索樹的后序遍歷序列（后序遍歷）
題目描述：輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。
思路：根據二叉搜索樹性質：結點值大于結點的左結點的數值，小于結點的右結點的數值來實現。
# -*- coding:utf-8 -*-
class Solution:def VerifySquenceOfBST(self, sequence):# write code hereif len(sequence)==0:return Falseroot = sequence[-1]i = 0for node in sequence[:-1]:if node > root:breaki += 1for node in sequence[i:-1]:if node < root:return Falseleft = Trueif i > 1:left = self.VerifySquenceOfBST(sequence[:i])right = True#i < (len(sequence)-1)以確保是二叉搜索樹if (i < (len(sequence)-1))and left:right = self.VerifySquenceOfBST(sequence[i:-1])return left and right二叉樹中和為某一值的路徑
題目描述：輸入一顆二叉樹的根節點和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。(注意: 在返回值的list中，數組長度大的數組靠前)
思路：遞歸，依據終止條件左結點=右結點=None且對應的根節點值是之前路徑的總和中差的最后一項值。在前序、中序和后序遍歷中只有前序遍歷是最先訪問根節點的，而且題中說在返回的list中數組長度大的數組在前，所以應該采用前序遍歷的方法。前序遍歷先訪問左子樹時，在每一個節點的根節點按照從左至右的順序進行訪問。將設定的值expectNumber與所經過的路徑中除去最后一個節點的值的和進行相減，然后將結果與遍歷的最后一個節點的值進行對比，如果相等的話則說明這條路徑是我們所想要的，然后記錄下來，返回ret。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:# 返回二維列表，內部每個列表表示找到的路徑def FindPath(self, root, expectNumber):# write code hereret = []def dfs(root,sum_,tmp):if root:if root.left==None and root.right == None:if root.val == sum_:tmp.append(root.val)ret.append(tmp[:])else:tmp.append(root.val)dfs(root.left,sum_-root.val,tmp[:])dfs(root.right,sum_-root.val,tmp[:])dfs(root,expectNumber,[])return ret二叉樹的深度
題目描述：輸入一棵二叉樹，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。
思路：遞歸，求得根節點的左子樹和右子樹的深度，最后再加1。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:def TreeDepth(self, pRoot):# write code hereif pRoot == None:return 0if pRoot.left == None and pRoot.right==None:return 1return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1平衡二叉樹
題目描述：輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。
思路：平衡二叉樹的定義：是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。根據定義來直接判斷。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:def IsBalanced_Solution(self, pRoot):# write code hereif pRoot == None:return Trueif abs(self.TreeDepth(pRoot.left)-self.TreeDepth(pRoot.right)) > 1:return Falsereturn self.IsBalanced_Solution(pRoot.left)
and self.IsBalanced_Solution(pRoot.right)def TreeDepth(self, pRoot):# write code hereif pRoot == None:return 0nLeft = self.TreeDepth(pRoot.left)nRight = self.TreeDepth(pRoot.right)return max(nLeft+1,nRight+1)#(nLeft+1 if nLeft > nRight else nRight +1)二叉樹的下一個結點
題目描述：給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點并且返回。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指針。
思路：判斷結點是左、右結點，然后按照中序遍歷的先左結點，后父結點，最后右結點的順序遍歷下一個結點。
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = None
class Solution:# 返回構造的TreeNode根節點def reConstructBinaryTree(self, pre, tin):# write code hereif len(pre)==0:return Noneroot=TreeNode(pre[0])TinIndex=tin.index(pre[0])root.left=self.reConstructBinaryTree(pre[1:TinIndex+1], tin[0:TinIndex])root.right=self.reConstructBinaryTree(pre[TinIndex+1:], tin[TinIndex+1:])return root對稱的二叉樹
題目描述：請實現一個函數，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的。
思路：遞歸判斷。注意和第12題的區別，這里不是生成一個鏡像的二叉樹，而是判斷已有的二叉樹是否是對稱的。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:def isSymmetrical(self, pRoot):# write code heredef is_same(p1,p2):if not p1 and not p2:return Trueif (p1 and p2) and p1.val==p2.val:return is_same(p1.left,p2.right) and is_same(p1.right,p2.left)return Falseif not pRoot:return Trueif pRoot.left and not pRoot.right:return Falseif not pRoot.left and pRoot.right:return Falsereturn is_same(pRoot.left,pRoot.right)序列化二叉樹
題目描述：請實現兩個函數，分別用來序列化和反序列化二叉樹。二叉樹的序列化是指：把一棵二叉樹按照某種遍歷方式的結果以某種格式保存為字符串，從而使得內存中建立起來的二叉樹可以持久保存。序列化可以基于先序、中序、后序、層序的二叉樹遍歷方式來進行修改，序列化的結果是一個字符串，序列化時通過 某種符號表示空節點（#），以！表示一個結點值的結束（value!）。二叉樹的反序列化是指：根據某種遍歷順序得到的序列化字符串結果str，重構二叉樹。
思路：序列化的過程：按照層序遍歷的方式查找空節點，然后由“#”進行替換。反序列化的過程：查找不是“#”的結點值，然后添加，否則是None。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:def __init__(self):self.index = -1def Serialize(self, root):# write code hereif root:return str(root.val) + ' ' +\self.Serialize(root.left) + \self.Serialize(root.right)else:return '# 'def Deserialize(self, s):# write code herel = s.split()self.index += 1if self.index >= len(s): return Noneif l[self.index] != '#':root = TreeNode(int(l[self.index]))root.left = self.Deserialize(s)root.right = self.Deserialize(s)else:return Nonereturn root結尾
親愛的讀者朋友：感謝您在繁忙中駐足閱讀本期內容！您的到來是對我們最大的支持??
正如古語所言："當局者迷，旁觀者清"。您獨到的見解與客觀評價，恰似一盞明燈💡，能幫助我們照亮內容盲區，讓未來的創作更加貼近您的需求。
若此文給您帶來啟發或收獲，不妨通過以下方式為彼此搭建一座橋梁： ? 點擊右上角【點贊】圖標，讓好內容被更多人看見 ? 滑動屏幕【收藏】本篇，便于隨時查閱回味 ? 在評論區留下您的真知灼見，讓我們共同碰撞思維的火花
我始終秉持匠心精神，以鍵盤為犁鏵深耕知識沃土💻，用每一次敲擊傳遞專業價值，不斷優化內容呈現形式，力求為您打造沉浸式的閱讀盛宴📚。
有任何疑問或建議？評論區就是我們的連心橋！您的每一條留言我都將認真研讀，并在24小時內回復解答📝。
愿我們攜手同行，在知識的雨林中茁壯成長🌳，共享思想綻放的甘甜果實。下期相遇時，期待看到您智慧的評論與閃亮的點贊身影?！
萬分感謝🙏🙏您的點贊👍👍、收藏?🌟、評論💬🗯?、關注??💚～
自我介紹：一線互聯網大廠資深算法研發（工作6年+），4年以上招聘面試官經驗（一二面面試官，面試候選人400+），深諳崗位專業知識、技能雷達圖，已累計輔導15+求職者順利入職大中型互聯網公司。熟練掌握大模型、NLP、搜索、推薦、數據挖掘算法和優化，提供面試輔導、專業知識入門到進階輔導等定制化需求等服務，助力您順利完成學習和求職之旅（有需要者可私信聯系）?
友友們，自己的知乎賬號為“快樂星球”，定期更新技術文章，敬請關注！????
)
