算法（5）：二叉樹

??終于到傻叉樹啦~ 這個是我想好好探討的一種數(shù)據(jù)結構，小伙子我覺得它有難度瓶竭，不管是前中后序以及層級遍歷督勺，還是各種遞歸迭代的妙用渠羞，總之，很酷智哀！
??加油加油堵未，怎么也得寫個十多篇算法系列才行~

目錄：
算法：附錄
 算法（1）：遞歸
 算法（2）：鏈表
 算法（3）：數(shù)組
 算法（4）：字符串
 算法（5）：二叉樹
 算法（6）：二叉查找樹
 算法（7）：隊列和堆棧（附贈BFS和DFS）
算法（8）：動態(tài)規(guī)劃
 算法（9）：哈希表
 算法（10）：排序
 算法（11）：回溯法
 算法（12）：位操作

??雖然本系列著重講算法，但還是需要個引子盏触，所以小編先簡單說一下啥是二叉樹渗蟹。二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）赞辩。如下圖所示雌芽，便是一個二叉樹結構。

二叉樹

??既然大家知道什么是二叉樹了辨嗽，那么我們首先來看一下二叉樹的前序遍歷（Pre-order Traversal）世落、中序遍歷（In-order Traversal）以及后序遍歷（Post-order Traversal）。

前序遍歷：先根節(jié)點糟需，再左節(jié)點屉佳，最后右節(jié)點。（也可以右左根洲押，然后翻轉）
中序遍歷：先左節(jié)點武花，再根節(jié)點，最后右節(jié)點杈帐。（也可以右根左体箕，然后翻轉）
后序遍歷：先左節(jié)點，在右節(jié)點挑童，最后根節(jié)點累铅。（也可以根右左，然后翻轉）

??說白了站叼，就是看遍歷根節(jié)點的先后順序娃兽。而不論是哪種遍歷方法，都是左節(jié)點比右節(jié)點先遍歷尽楔。當然投储，如果按照括號里給出的操作方式，也可以得到相同結果~ 那么翔试，既然知道了如何遍歷轻要，根據(jù)上面的二叉樹圖复旬，大家可以寫出不同遍歷方法的的結果嗎垦缅？
??算了，我也不知道你們會不會驹碍，索性先把答案給各位放出來壁涎，有興趣的小伙伴可以先試試自己寫凡恍，然后和我給的答案對照一下~ ~~蛤？你說你的答案跟我的不一樣怔球？那肯定是你錯了......~~

前序遍歷結果：F B A D C E G I H
中序遍歷結果：A B C D E F G H I
后序遍歷結果：A C E D B H I G F

??既然有這三種遍歷方法嚼酝，那么，它們都有何作用呢竟坛？什么時候用前序遍歷闽巩，什么時候又需要后序遍歷呢？大家且聽我慢慢道來：

前序遍歷：在第一次遍歷到節(jié)點時就執(zhí)行操作担汤，一般只是想遍歷執(zhí)行操作（或輸出結果）可選用先序遍歷涎跨，如輸出某個文件夾下所有文件與文件夾的名稱：遍歷文件夾，先輸出文件夾名崭歧，然后再依次輸出該文件夾下的所有文件(包括子文件夾)隅很，如果有子文件夾，則再進入該子文件夾率碾，輸出該子文件夾下的所有文件名叔营。這是一個典型的先序遍歷過程。
中序遍歷：對于二分搜索樹所宰，中序遍歷的操作順序（或輸出結果順序）是符合從小到大（或從大到腥拮稹）順序的，故要遍歷輸出排序好的結果需要使用中序遍歷仔粥。除此之外垒酬，還有中綴表達式，一個通用的算術或邏輯公式表示方法件炉。符合人類的邏輯（例：2 + 3）.
后序遍歷：后續(xù)遍歷的特點是執(zhí)行操作時勘究，肯定已經(jīng)遍歷過該節(jié)點的左右子節(jié)點。1. 故適用于進行破壞性操作的情況斟冕，比如刪除節(jié)點（因為我們在刪除節(jié)點時需要先刪除左右兩子節(jié)點口糕，再刪除該節(jié)點）。2. 其次磕蛇，如果我們要統(tǒng)計文件夾大小景描，也需要后序遍歷來實現(xiàn)：若要知道某文件夾的大小必須先知道該文件夾下所有文件的大小，如果有子文件夾秀撇，若要知道該子文件夾大小超棺，必須先知道子文件夾所有文件的大小。這是一個典型的后序遍歷過程呵燕。3. 既然有了中綴表達式棠绘，那么也有相應的后綴表達式，~~當然也有前綴表達式，~~后綴表達式是一種不需要括號的表達法氧苍。符合計算機的邏輯（例：2 3 +）夜矗。

??關于中綴和后綴表達式，我愿意再給大家詳細說明一下让虐，各位官爺請看下圖：

數(shù)學表達式

??如果我們用中序遍歷紊撕，那么可以非常迅速的得到4 * 7 - 2 + 5這么一個式子。但是赡突，每個運算符的優(yōu)先級对扶，很難寫程序去判定。比如惭缰，我們想表示4 * （7 - 2） + 5的式子辩稽，即讓減號的優(yōu)先級最高，該如何計算呢从媚？這時逞泄，就需要后綴表達式出場了。我們可以得到4 7 2 - * 5 +這么一串結果拜效。屏幕前的你們可能已經(jīng)開始認真思考喷众，內心也產(chǎn)生了寶貴的想法：~~zhe ta ma shen me ji ba wan yi er...~~ 但是計算機可是如獲至寶，開心的像個兩百斤的孩子一樣紧憾。因為它可以很輕易的算出結果：建立一個棧（stack到千，這玩意遵循LIFO，即 last in赴穗，first out 原則）憔四，不停的將節(jié)點值壓進棧里，當節(jié)點值為運算符時般眉，它便彈出最新壓入的值做運算了赵，并將結果再壓入棧中。so easy甸赃！~~哪里不會點哪里柿汛，媽媽再也不用擔心我的學習啦...~~

??洋洋灑灑上千字，沒點代碼怎么行埠对。

問題1：二叉樹前序遍歷（Binary Tree Preorder Traversal）
輸入：二叉樹根節(jié)點
輸出：[1, 2, 4, 3, 5]

??前序遍歷比較簡單络断，一邊遍歷，一邊裝節(jié)點值项玛。以下代碼用了非遞歸方式貌笨，大伙可以試試如何用遞歸寫~（遞歸寫起來方便些，但是執(zhí)行效率會偏低）

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def preorderTraversal(root):
    cur_node = root
    stack = []
    res = []

    while stack or cur_node:
        if cur_node:
            res.append(cur_node.val)
            stack.append(cur_node)
            cur_node = cur_node.left
        else:
            cur_node = stack.pop()
            cur_node = cur_node.right
    return res

if __name__ == '__main__':
    node = head = TreeNode(1)
    node.left =  TreeNode(2)
    node.right = TreeNode(3)
    node.left.right = TreeNode(4)
    node.right.left = TreeNode(5)

    ans = preorderTraversal(head)
    print(ans)

問題2：二叉樹中序遍歷（Binary Tree Inorder Traversal）
輸入：同上
輸出：[2, 4, 1, 5, 3]

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def inorderTraversal(root: TreeNode) -> list:
    cur_node = root
    stack = []
    res = []

    while stack or cur_node:
        if cur_node:
            stack.append(cur_node)
            cur_node = cur_node.left
        else:
            cur_node = stack.pop()
            res.append(cur_node.val)
            cur_node = cur_node.right
    return res

if __name__ == '__main__':
    node = head = TreeNode(1)
    node.left =  TreeNode(2)
    node.right = TreeNode(3)
    node.left.right = TreeNode(4)
    node.right.left = TreeNode(5)

    ans = inorderTraversal(head)
    print(ans)

問題3：二叉樹后序遍歷（Binary Tree Postorder Traversal）
輸入：同上
輸出：[4, 2, 5, 3, 1]
??后序遍歷的話運用了倒裝方式襟沮，先裝節(jié)點值锥惋，再裝右節(jié)點昌腰，最后裝左節(jié)點。返回結果時將列表翻轉即為答案净刮。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def postorderTraversal(root: TreeNode) ->list:
    cur_node = root
    stack = []
    res = []

    while stack or cur_node:
        if cur_node:
            stack.append(cur_node)
            res.append(cur_node.val)
            cur_node = cur_node.right
        else:
            cur_node = stack.pop()
            cur_node = cur_node.left
    return res[::-1]

if __name__ == '__main__':
    node = head = TreeNode(1)
    node.left =  TreeNode(2)
    node.right = TreeNode(3)
    node.left.right = TreeNode(4)
    node.right.left = TreeNode(5)

    ans = postorderTraversal(head)
    print(ans)

問題4：二叉樹逐層遍歷（Binary Tree Level Order Traversal）。這里是將二叉樹一層一層硅则，從左往右遍歷淹父，用到了廣度優(yōu)先搜索（Breadth-First Search）的思想。
輸入：同上
輸出：[[1], [2, 3], [4, 5]]

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def levelOrder(root: TreeNode) -> list:
    if root == None: return []
    queue = [[root]]
    res = []
    while queue:
        curlevel = queue.pop()
        newlevel = []
        val = []
        for node in curlevel:
            if node:
                val.append(node.val)
                newlevel.append(node.left)
                newlevel.append(node.right)
        if newlevel != []:
            queue.append(newlevel)
        if val != []:
            res.append(val)
    return res

if __name__ == '__main__':
    node = head = TreeNode(1)
    node.left =  TreeNode(2)
    node.right = TreeNode(3)
    node.left.right = TreeNode(4)
    node.right.left = TreeNode(5)

    ans = levelOrder(head)
    print(ans)

問題5：判斷一個二叉樹是否為對稱二叉樹怎虫。
輸入：二叉樹暑认，如下所示：
輸出：True

代碼如下（就我個人理解，應該是屬于自頂向下的遞歸法大审，如果不滿足先決條件的話蘸际，將不再繼續(xù)遞歸，直接返回False結果）：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def isSymmetric(root: TreeNode) -> bool:
    def helper(left, right):
        if not left and not right: return True
        if left and right and left.val == right.val:
            return helper(left.right, right.left) and helper(left.left, right.right)
        return False

    if not root: return True
    return helper(root.left, root.right)

if __name__ == '__main__':
    node = head = TreeNode(1)
    node.left =  TreeNode(2)
    node.right = TreeNode(2)
    node.left.right = TreeNode(3)
    node.right.left = TreeNode(3)

    ans = isSymmetric(head)
    print(ans)

自頂向下（top-down）和自底向上（bottom-up）的遞歸方法

自頂向下：在每次遞歸調用時徒扶，我們利用該節(jié)點的信息計算出某些值粮彤，然后通過遞歸調用將這些值（這些傳遞的值一般是全局變量）傳遞給它的子節(jié)點，一直到葉子節(jié)點姜骡。
自底向上：在使用遞歸法時导坟，我們先對子節(jié)點使用遞歸函數(shù)，然后讓子節(jié)點返回一些值（這時一般就不傳遞全局變量）圈澈，最后我們利用子節(jié)點返回的值進行計算惫周。

舉個小小例子：計算某個二叉樹的深度。（如果是屏幕面前的你康栈，你會如何計算呢递递？~~感覺自己講話方式好 zhi zhang，啥么，登舞，~~）

如果是自頂向下（此時從上往下樹的深度執(zhí)行加一操作)：

1. return if root is null
2. if root is a leaf node:
3.      answer = max(answer, depth)         // update the answer if needed
4. maximum_depth(root.left, depth + 1)      // call the function recursively for left child
5. maximum_depth(root.right, depth + 1)     // call the function recursively for right child

這個時候你又想自底向上了（這時是從下往上深度不停加一）：

1. return 0 if root is null                 // return 0 for null node
2. left_depth = maximum_depth(root.left)
3. right_depth = maximum_depth(root.right)
4. return max(left_depth, right_depth) + 1  // return depth of the subtree rooted at root

??大家可以看出，如果我們可以得到該節(jié)點的信息（如節(jié)點深度為前面總共深度再加一）悬荣，并且這些信息可以幫助到子節(jié)點的計算逊躁，那么就可以考慮自頂向下法；如果我們知道子節(jié)點的結果隅熙，并通過它來計算該節(jié)點的結果稽煤，那么便可以使用自底向上法∏羝荩總而言之一句話酵熙，這玩意不簡單吶。

例題6：歡迎大家收看例題沒完沒了系列之路徑求和(Path Sum)驰坊。給定一顆二叉樹匾二，如果從根節(jié)點到某個葉子節(jié)點這條路徑上的值之和等于目標值’target‘，則返回True，否則返回False察藐。
輸入：見例題1
輸出：True（1+2+4=7）皮璧，F(xiàn)alse，True（1+3+5=9）
這個代碼屬于自頂向下方法：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def hasPathSum(root: TreeNode, target: int) -> bool:
    def helper(node, ans):
        if not node: return False
        if not node.left and not node.right: return ans + node.val == target
        return helper(node.left, ans + node.val) or helper(node.right, ans + node.val)

    return helper(root, 0)

if __name__ == '__main__':
    node = head = TreeNode(1)
    node.left =  TreeNode(2)
    node.right = TreeNode(3)
    node.left.right = TreeNode(4)
    node.right.left = TreeNode(5)

    for i in range(7,10):
        print(hasPathSum(head,i))

例題7：根據(jù)中序遍歷和后序遍歷的列表分飞，構建該二叉樹悴务。
輸入：inorder = [9,3,15,20,7]，postorder = [9,15,7,20,3]
輸出：二叉樹譬猫，如下所示讯檐。

??對于一棵樹的中序遍歷，根節(jié)點肯定處于遍歷結果的中間（假設這棵樹有左子樹）染服，后序遍歷的時候根節(jié)點肯定是最后一個遍歷的元素别洪。所以我們在后序遍歷列表當中，依次從最后位置取出根節(jié)點柳刮，并且找到該根節(jié)點在中序遍歷列表當中的位置挖垛。此時，該位置左邊就是這棵樹的左子樹元素秉颗，右邊元素就是這棵樹的右子樹元素晕换。如此遞歸下去，便可得到想要結果~
??大家可以思考一個問題站宗，那就是根據(jù)中序遍歷和前序遍歷是否也可以構建出唯一的二叉樹闸准？（答案是可以，做法也是幾乎一樣梢灭，在前序遍歷列表當中從前往后取根節(jié)點就可以~）那么前序和后序遍歷能構建唯一的一棵二叉樹嗎夷家？（答案是不行，因為你無法判斷節(jié)點屬于左子樹還是右子樹）

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def buildTree( inorder: list, postorder: list) ->TreeNode:
    if not inorder or not postorder: return
    val = postorder.pop()
    node = TreeNode(val)
    idx = inorder.index(val)

    node.right = buildTree(inorder[idx + 1:], postorder)
    node.left = buildTree(inorder[:idx], postorder)

    return node

def preorder(head):
    def helper(node,ans):
        if not node:return
        ans.append(node.val)
        helper(node.left,ans)
        helper(node.right,ans)

    ans =[]
    helper(head,ans)
    return ans

if __name__ == '__main__':
    inorder = [9, 3, 15, 20, 7]
    postorder = [9, 15, 7, 20, 3]
    head = buildTree(inorder,postorder)

    ans = preorder(head)
    print(ans)

例題8：輸入兩棵二叉樹A敏释，B库快，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）
輸入：A

輸入：B

    20
   /  \
  15   7

輸出：True

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot1 or not pRoot2:
            return False
        return 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 True
        if not A or A.val != B.val:
            return False
        return self.is_subtree(A.left,B.left) and self.is_subtree(A.right, B.right)

求求求求求钥顽，點贊和關注义屏！