樹的題目通常可以用遞歸解決，遞歸過程的本質(zhì)是棧，因而理論上遞歸也可以用循環(huán)加堆棧（或者隊列）解決
關(guān)于遞歸
遞歸非常容易讓人思路混亂盟榴，看到網(wǎng)上有一種思路覺得很有用，就是假設(shè)子問題已經(jīng)完美處理婴噩，你只需思考最終問題的處理思路擎场，子問題的處理思路和最終問題的處理思路一樣，這樣思路就會清晰很多几莽。
以下代碼示例均為python版本
題目一：從上往下打印二叉樹
題目描述：
從上往下打印出二叉樹的每個節(jié)點迅办，同層節(jié)點從左至右打印。
算法思路：
很明顯用層次遍歷就可以解決章蚣，即廣度遍歷站欺，從上往下打印，即每一層打印完之后需要按照父節(jié)點們的順序繼續(xù)打印子節(jié)點纤垂，
符合隊列先進先出的特點矾策，因而需要借助隊列+循環(huán)判斷就可以解決。
即借助隊列峭沦，將根結(jié)點加入隊列贾虽，每遍歷到一個結(jié)點，將該結(jié)點移除出隊列并將該結(jié)點的左右節(jié)點加入隊列吼鱼，重復(fù)這個過程蓬豁，直至隊列為空绰咽。
關(guān)鍵字：隊列 循環(huán)
代碼如下
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回從上到下每個節(jié)點值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
if root is None:
return []
tempnode = []
tempnode.append(root)
valres = []
while (len(tempnode) > 0):
node = tempnode.pop(0)
valres.append(node.val)
if node.left is not None:
tempnode.append(node.left)
if node.right is not None:
tempnode.append(node.right)
return valres
題目二：二叉樹的鏡像
題目描述：
操作給定的二叉樹地粪，將其變換為源二叉樹的鏡像取募。
如下圖：
算法思路：
從題目可以知道二叉樹的鏡像其實可以看成是左右子結(jié)點交換的過程，如下圖：
因而我們在前序遍歷（順序為根子樹->左子樹->右子樹）的基礎(chǔ)上驶忌，交換當前結(jié)點的左右子結(jié)點矛辕，就可以完成二叉樹的鏡像。
代碼如下
# -*- coding:utf-8 -*-
'''
樹的鏡像
思路：遞歸交換左右結(jié)點
'''
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回鏡像樹的根節(jié)點
def Mirror(self, root):
# write code here
if root is None:
return root
if root.left is None and root.right is None:
return root
tempNode = root.left
root.left = root.right
root.right = tempNode
self.Mirror(root.left)
self.Mirror(root.right)
關(guān)鍵字：遞歸 前序遍歷
題目三：二叉搜索樹的后序遍歷序列
題目描述：
輸入一個整數(shù)數(shù)組付魔，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果聊品。如果是則返回True，否則返回False几苍。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同翻屈。
算法思路：
二叉搜索樹：
是指一棵空樹或者具有下列性質(zhì)的二叉樹：
若任意節(jié)點的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值妻坝；
若任意節(jié)點的右子樹不空伸眶，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；
任意節(jié)點的左刽宪、右子樹也分別為二叉查找樹厘贼；
沒有鍵值相等的結(jié)點。
后序遍歷順序：左子樹->右子樹->根結(jié)點
1）遞歸方法
由后序遍歷順序可知圣拄，序列的最后一個元素為根結(jié)點嘴秸，根據(jù)二叉搜索樹的特點可知，左子樹的每個非空結(jié)點都不大于根結(jié)點庇谆，右子樹的每個非空結(jié)點都不小于根結(jié)點岳掐，題目中規(guī)定序列中各個結(jié)點都不重復(fù)，因此可以確定題目中給的測試用例中饭耳，左子樹的每個結(jié)點勢必都小于根結(jié)點串述，右子樹的每個結(jié)點勢必都大于根結(jié)點。
因此從左往右查找寞肖，找到第1個大于根結(jié)點的值則說明這個元素往左邊的元素是左子樹纲酗，該元素及往右邊的元素到最后一個結(jié)點前為右子樹。
如果左子樹有任一元素大于根結(jié)點新蟆，或者右子樹有任一元素小于根結(jié)點耕姊，說明該序列不為二叉搜索樹遍歷序列。
以此方法進行遞歸判斷栅葡。
圖中最后一個元素8為根結(jié)點，元素9為從左往右序列中第一個大于根結(jié)點的值尤泽，以9往左為左子樹欣簇，9和9往右到最后一個元素8前為右子樹规脸。
觀察可知 如果符合二叉搜索樹，則右子樹序列元素都比根結(jié)點大
左右子序列以此方法遞歸可判斷熊咽。
代碼如下
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if sequence is None or len(sequence) == 0:
return False
return self.VerifyBST(sequence)
def VerifyBST(self,verifys):
if len(verifys) <= 1: # 只剩根結(jié)點
return True
root = verifys[-1]
temps = verifys[:-1]
lefts = []
rights = []
for i in range(len(temps)):
if temps[i] > root:
lefts = temps[0:i]
if i <= len(temps) - 1:
rights = temps[i:-1]
break
else:
lefts = temps
for v in rights:
if v < root:
return False
return self.VerifyBST(lefts) and self.VerifyBST(rights)
2）非遞歸方法（拍迹客網(wǎng)上看到的）
大致思路是根據(jù)后序遍歷，將當前結(jié)點A作為根結(jié)點横殴，遍歷結(jié)點A前面序列的值被因，如果當前序列元素值小于結(jié)點A的值，并且前一序列元素值也大于結(jié)點A的值 說明不是二叉搜索樹衫仑。
參考鏈接 爬嬗耄客網(wǎng)
圖片侵刪
關(guān)鍵字：遞歸 二叉搜索樹特點
題目四：二叉樹中和為某一值的路徑
題目描述：
輸入一顆二叉樹的根節(jié)點和一個整數(shù)，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑文狱。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑粥鞋。
算法思路：
路徑指的是樹的根結(jié)點到葉結(jié)點所經(jīng)過的結(jié)點，因此題目其實是求從根結(jié)點到某一葉結(jié)點的路徑上所有結(jié)點的和是否為題目中要求的值瞄崇。
因為計算是從根結(jié)點開始呻粹，所以其實可以看成是樹的前序遍歷的基礎(chǔ)上計算路徑和，由于題目要求打印出路徑苏研，因而每次遍歷結(jié)點需要記錄下當前結(jié)點等浊，到達葉結(jié)點時需要判斷該路徑是否符合條件，當遞歸回退到上一個結(jié)點時需要從路徑中移除當前結(jié)點即路徑的最后一個結(jié)點摹蘑，記錄路徑可以用堆棧筹燕。
示例：
根結(jié)點到葉結(jié)點加入堆棧 ，堆棧中加入序列為 10纹蝴，5庄萎， 4；
10+5+4不等于22塘安，不記錄路徑糠涛；
彈出4，回到父結(jié)點5兼犯，堆棧序列 10,5忍捡；
右葉結(jié)點7 進棧 ，堆棧序列 10,5,7,等于22 切黔，記錄路徑砸脊；
彈出7，回到5纬霞；
彈出5凌埂，回到10；
葉結(jié)點12進棧诗芜，堆棧序列 10,12 等于 22 瞳抓，記錄路徑埃疫；
所以符合條件的路徑為[10,5,7]和[10,12]。
# -*- coding:utf-8 -*-
"""
二叉樹中和為某一值的路徑
"""
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回二維列表孩哑，內(nèi)部每個列表表示找到的路徑
def FindPath(self, root, expectNumber):
return self.RealFindPath(root, 0, expectNumber, [], [])
def RealFindPath(self, root, sum, expectNumber, path, allpath):
if root is None:
return allpath
sum += root.val
path.append(root.val)
if root.left is None and root.right is None:
if sum == expectNumber:
allpath.append(path[:])
if root.left:
self.RealFindPath(root.left, sum, expectNumber, path, allpath)
if root.right:
self.RealFindPath(root.right, sum, expectNumber, path, allpath)
# 回退到上個結(jié)點前彈出當前元素
if len(path) > 0:
num = path.pop() # 彈出末尾元素
sum = sum - num
return allpath
關(guān)鍵字：遞歸 堆棧
題目五：對稱的二叉樹
題目描述：
請實現(xiàn)一個函數(shù)栓霜，用來判斷一顆二叉樹是不是對稱的。注意横蜒，如果一個二叉樹同此二叉樹的鏡像是同樣的胳蛮，定義其為對稱的。
算法思路：
遞歸方法：
如下圖丛晌，由對稱的二叉樹觀察得知仅炊，同一父節(jié)點的左子結(jié)點（6）的左結(jié)點（矩形1）和右子結(jié)點（6）的右結(jié)點（矩形1）如果不相等（一個為空另一個不為空也是不相等），或者同一父節(jié)點的左子結(jié)點（6）的右結(jié)點（圓形3）和右子結(jié)點（6）的左結(jié)點（圓形3）如果不相等（一個為空另一個不為空也是不相等）茵乱，則說明該二叉樹不為對稱二叉樹茂洒。
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isSymmetrical(self, pRoot):
if pRoot is None:
return True
return self.IsRealSymmetrical(pRoot.left, pRoot.right)
def IsRealSymmetrical(self, Lroot, Rroot):
if (Lroot and Rroot is None) or (Rroot and Lroot is None):
return False
if Lroot is None and Rroot is None:
return True
if Lroot.val != Rroot.val:
return False
return self.IsRealSymmetrical(Lroot.left, Rroot.right) and self.IsRealSymmetrical(Lroot.right, Rroot.left)
關(guān)鍵字：遞歸 非遞歸
題目六：重建二叉樹
題目描述：
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹瓶竭。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字督勺。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回斤贰。
算法思路：
由前序序列和中序序列可得二叉樹智哀。由前序遍歷的遍歷過程可以知道，前序序列的第1個元素為根結(jié)點荧恍，在中序序列中找到根結(jié)點瓷叫，序列中根結(jié)點往左為左子樹，根結(jié)點往右為右子樹送巡。根據(jù)此方法遞歸可重建二叉樹摹菠，遞歸的本質(zhì)是棧（先進后出），因而最后遞歸返回的結(jié)點即為根結(jié)點骗爆。
關(guān)鍵字：遞歸
==============================
發(fā)現(xiàn)一個好玩的項目 ~
https://github.com/Wscats/piano
