這是一個(gè)系列豹障，關(guān)于二叉樹的冯事，這個(gè)吧，接下來(lái)幾天重點(diǎn)看這個(gè)了血公。
這個(gè)系列昵仅，把前中后都講了吧

1.題目

給定一個(gè)二叉樹，返回它的 前序/中序/后序 遍歷。
要求摔笤，遞歸比較簡(jiǎn)單够滑，用分治的思路解決。

2.解析

（1）遞歸
遞歸簡(jiǎn)單吕世，定義一個(gè)函數(shù)彰触，滿足下面條件：
注意遍歷起名字都站在父節(jié)點(diǎn)的視角
1）先序遍歷：
先父再左再右
2）中序遍歷：
先左再父再右
3）后序遍歷：
先左再右再父
這個(gè)實(shí)現(xiàn)簡(jiǎn)單，就是一個(gè)先后順序的問題命辖，也就是list再哪append的問題况毅。
（2）循環(huán)
循環(huán)記住一個(gè)思路即可：
樹的遍歷基本都要用到棧這個(gè)數(shù)據(jù)結(jié)構(gòu)。
1）先序遍歷
先序遍歷的想法就是尔艇，每次都先更新父節(jié)點(diǎn)的值尔许，因此就把a(bǔ)ppend這個(gè)放在第一個(gè)循環(huán)里，這樣就保證先中再左再右漓帚。
2）中序遍歷
一步步來(lái)思考母债，先走左邊，再存現(xiàn)在尝抖，最后走右邊毡们。一個(gè)棧，每次push左節(jié)點(diǎn)昧辽，直至為空衙熔，注意壓進(jìn)去的還是一顆樹。然后這個(gè)棧每次出一個(gè)左節(jié)點(diǎn)搅荞，來(lái)個(gè)列表存值红氯，然后遍歷他的右節(jié)點(diǎn)。直到stack和root都是空咕痛。
3）后序遍歷
后序遍歷其實(shí)是先序遍歷的逆過程痢甘。首先走左節(jié)點(diǎn)，然后走右節(jié)點(diǎn)茉贡，然后走中間節(jié)點(diǎn)塞栅，怎么控制右節(jié)點(diǎn)呢就是把左節(jié)點(diǎn)入棧，然后遍歷完右節(jié)點(diǎn)腔丧，遍歷左節(jié)點(diǎn)放椰，最后做個(gè)倒序列。

3.python代碼

#節(jié)點(diǎn)定義
class Node:
    def __init__(self,  x):
        self.val = x
        self.left = None
        self.right = None
#遞歸
#先序遍歷
class Solution:
    def preorderTraversal(self, root):
        if not root:
            return []
        return [root.val] +self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
#中序遍歷
class Solution:
    def preorderTraversal(self, root):
        if not root:
            return []
        return self.preorderTraversal(root.left) + [root.val] + self.preorderTraversal(root.right)
#后序遍歷
class Solution:
    def preorderTraversal(self, root):
        if not root:
            return []
        return self.preorderTraversal(root.left) + self.preorderTraversal(root.right)+ [root.val] 
#循環(huán)
#先序遍歷
class Solution:
    def preorderTraversal(self, root):
        stack = []
        listout = []
        cur = root
        while cur or stack:
            if cur:
                listout.append(cur.val)
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                cur = cur.right
                # if cur:
                #     listout.append(cur.val)
        return listout
#中序遍歷
class Solution:
    def inorderTraversal(self, root):
        stack = []
        listout = []
        cur = root
        while stack or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                listout.append(cur.val)
                cur = cur.right
        return listout
#后序遍歷
    class Solution:
        def postorderTraversal(self, root):
            stack = []
            listout = []
            cur = root
            while cur or stack:
                if cur:
                    listout.append(cur.val)
                    stack.append(cur.left)
                    cur = cur.right
                else:
                    cur = stack.pop()
            return listout[::-1]