書籍推薦

《大話數(shù)據(jù)結(jié)構(gòu)》——https://www.loneway.ren/book/20006

二叉樹的遍歷

二叉樹的遍歷方式有兩類：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。

深度優(yōu)先遍歷

深度優(yōu)先遍歷是指順著某一條路徑盡可能的向前探索术唬，必要的時候(探索到葉子節(jié)點)回溯焚志。

遍歷順序:

• 先根序遍歷(DLR)
• 中根序遍歷(LDR)
• 后根序遍歷(LRD)

實現(xiàn)方法:

• 遞歸方法

    給定一個二叉樹朵栖，返回它的中序 遍歷责循。
    示例:

    輸入: [1,null,2,3]
       1
        \
         2
        /
       3

    輸出: [1,3,2]

    來源：力扣（LeetCode）
    鏈接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution(object):
        def inorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            assert isinstance(root, TreeNode). TypeError
            if not root:
                return []
            return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

• 循環(huán)迭代方法

先根序遍歷(DLR):

    class Solution(object):
        def inorderTraversal(self, root):
            i = root
            result = []
            stack = []
            while i or stack: # 判斷整棵樹是否遍歷完成
                while i: # 判斷是否達(dá)到葉子節(jié)點
                    result.append(i.val) # 先遍歷根節(jié)點
                    stack.append(i.right) # 右子樹入棧撮珠，待會兒遍歷
                    i = i.left # 深入左子樹
                i = stack.pop() # 取出右子樹
            return result


中根序遍歷(LDR):

    class Solution(object):
        def inorderTraversal(self, root):
            i = root
            result = []
            stack = []
            while i or stack:
                while i:
                    stack.append(i)
                    i = i.left
                i = stack.pop()
                result.append(i.val)
                i = i.right
            return result

后根序遍歷(LRD):

    class Solution(object):
        def inorderTraversal(self, root):
            i = root
            result = []
            stack = []
            while i or stack:
                while i:
                    stack.append(i)
                    i = i.left or i.right
                i = stack.pop()
                result.append(i.val)
                if stack and i == stack[-1].left:
                    i = stack[-1].right
                else:
                    i = None
            return result

廣度優(yōu)先遍歷

廣度優(yōu)先遍歷是指在所有子樹路徑上齊頭并進(jìn)歌粥。

遍歷順序:

• 層次遍歷

實現(xiàn)方法

• 隊列循環(huán)迭代

    from Queue import Queue
    class Solution(object):
        def inorderTraversal(self, root):
            result = []
            q = Queue()
            q.input(root)
            while not q.empty():
                item = q.get()
                if item:
                    if item.left:
                        q.put(item.left)
                    if item.right:
                        q.put(item.right)
                    result.append(item.val)
            return result

• 雙層列表迭代

    class Solution(object):
        def inorderTraversal(self, root):
            result = []
            if not root:
                return result
            cur_nodes = [root]
            while cur_nodes:
                sub_result = []
                next_nodes = []
                for node in cur_nodes:
                    if node:
                        sub_result.append(node.val)
                        if node.left:
                            next_nodes.append(node.left)
                        if node.right:
                            next_nodes.append(node.right)  
                result.append(sub_result)
                cur_nodes = next_nodes
            return result

問題變種

• 根據(jù)先根序遍歷和中根序遍歷結(jié)果塌忽，恢復(fù)一顆二叉樹

    根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。

    注意:
    你可以假設(shè)樹中沒有重復(fù)的元素失驶。

    例如土居，給出

    前序遍歷 preorder = [3,9,20,15,7]
    中序遍歷 inorder = [9,3,15,20,7]
    返回如下的二叉樹：

        3
       / \
      9  20
        /  \
       15   7


    來源：力扣（LeetCode）
    鏈接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None

    class Solution(object):
        def buildTree(self, preorder, inorder):
            """
            :type preorder: List[int]
            :type inorder: List[int]
            :rtype: TreeNode
            """
            if not preorder:
                return None
            root = TreeNode(preorder[0])
            mid = inorder.index(preorder[0])
            root.left = self.buildTree(preorder[1: mid+1], inorder[:mid])
            root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
            return root