二叉樹前中後序周遊—遞歸版和疊代版

Table of Contents

簡介

二叉樹的前序周遊

二叉樹的中序周遊

二叉樹的後序周遊

本部落格隻用于自身學習，如有錯誤，虛心求教！！！

簡介

    1

   /  \

  2   3

 /  \      \

4 5        6

• 層次周遊順序：[1 2 3 4 5 6]
• 前序周遊順序：[1 2 4 5 3 6]
• 中序周遊順序：[4 2 5 1 3 6]
• 後序周遊順序：[4 5 2 6 3 1]

層次周遊使用 BFS 實作，利用的就是 BFS 一層一層周遊的特性；而前序、中序、後序周遊利用了 DFS 實作。

前序、中序、後序遍隻是在對節點通路的順序有一點不同，其它都相同。

① 前序

void dfs(TreeNode root) {
    visit(root);
    dfs(root.left);
    dfs(root.right);
}
           

② 中序

void dfs(TreeNode root) {
    dfs(root.left);
    visit(root);
    dfs(root.right);
}
           

③ 後序

void dfs(TreeNode root) {
    dfs(root.left);
    dfs(root.right);
    visit(root);
}
           

二叉樹的前序周遊

144. 二叉樹的前序周遊

給定一個二叉樹，傳回它的 前序 周遊。

 示例:

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

1

   \

    2

  /

3

輸出: [1,2,3]

解法1-遞歸版：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        #遞歸版
        self.res = []
        self.treeTraversal(root)
        return self.res
    def treeTraversal(self, root):
        if not root:
            return
        self.res.append(root.val)
        self.treeTraversal(root.left)
        self.treeTraversal(root.right)
           

解法2-疊代版：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # 疊代版
        res = []
        stack = [root]
        while stack:
            node  = stack.pop()
            if node:
                res.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
        return res
           

二叉樹的中序周遊

94. 二叉樹的中序周遊

給定一個二叉樹，傳回它的中序 周遊。

示例:

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

1

  \

   2

/

3

輸出: [1,3,2]

解法1-遞歸版：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.res = []
        self.dfs(root)
        return self.res
        
    def dfs(self, root):
        if not root:
            return
        self.dfs(root.left)
        self.res.append(root.val)
        self.dfs(root.right)
           

解法2-疊代版：

先把疊代到最左邊的葉子節點，把所有途中的root放進stack，當左邊走不通了，開始往res裡面存數，并往右邊走。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # 疊代版
        res = []
        stack = []
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                node = stack.pop()
                res.append(node.val)
                root = node.right
        return res
           

二叉樹的後序周遊

145. 二叉樹的後序周遊

給定一個二叉樹，傳回它的 後序 周遊。

示例:

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

1

  \

   2

/

3

輸出: [3,2,1]

解法1：遞歸版

# 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 postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.res = []
        self.dfs(root)
        return self.res
    
    def dfs(self, root):
        if not root: return
        self.dfs(root.left)
        self.dfs(root.right)
        self.res.append(root.val)
           

解法2：

前序周遊為 root -> left -> right，後序周遊為 left -> right -> root。可以修改前序周遊成為 root -> right -> left，那麼這個順序就和後序周遊正好相反。

# 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 postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = [root]
        while stack:
            node  = stack.pop()
            if node:
                res.append(node.val)
                stack.append(node.left)
                stack.append(node.right)
        return res[::-1]
           

解法3：

Stack (利用Flag)

每次往Stack裡面儲存的順序是，先存儲目前root，然後right，最後left，這樣當pop到最左邊葉子節點的時候，就為第一個print的數，因為我們每次pop完之後的root之後還會用到，是以這裡利用flag，每次及時使用完root也将root重新放回stack，在之後pop過程中再檢查flag，如果visited過，則不再放回stack。

# 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 postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res, stack = [], [(root, False)]
        while stack:
            node, visited = stack.pop()
            if node:
                if visited:
                    # add to result if visited
                    res.append(node.val)
                else:
                    # post-order
                    stack.append((node, True))
                    stack.append((node.right, False))
                    stack.append((node.left, False))
        return res