二叉樹周遊(Python)

周遊二叉樹

#0 GitHub

https://github.com/Coxhuang/binary-tree-traversal

#1 環境

Python3.7.3           

複制

#2 開始

#2.1 層次周遊

#1 思路分析

#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 levelOrderBottom(self, root):
        """
        層次周遊
        :param root: 根節點
        :return: list_node -> List 
        """

        queue_node = [root]  # 隊列
        list_node = []  # 中序周遊存放結果清單

        while queue_node:  # 隊列不為空,一直循環

            node = queue_node.pop()  # 出隊
            if not node: # 節點為空, 從頭開始, 不把空節點放入結果清單 
                continue
            list_node.append(node.val) # 把節點數值存放到結果清單 
            queue_node.insert(0, node.left) # 左節點先入隊 
            queue_node.insert(0, node.right) # 右節點後入隊 

        print(list_node) 
        return list_node           

複制

#3 測試

輸出

# 層次周遊
[3, 9, 20, 15, 7]           

複制

#2.2 先序周遊

#1 思路

#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 levelOrderBottom(self, root):
        """
        先序周遊
        :param root: 根節點
        :return: list_node -> List
        """
        stack_node = [root]  # 棧
        list_node = []  # 先序周遊結果存放清單

        while stack_node: # 棧不為空
            node = stack_node.pop() # 棧頂節點出棧
            if not node: # 節點為空
                continue
            list_node.append(node.val) # 把不為空的節點數值存到清單
            stack_node.append(node.right) # 右節點先壓棧
            stack_node.append(node.left) # 左節點後壓棧
        print(list_node)
        return list_node
    
    def preOrderBottom_re(self, root):
        """
        先序周遊 遞歸
        :param root: 根節點
        :return: list_node -> List
        """
        
        if not root:
            return None
        print(root.val)
        self.preOrderBottom_re(root.left)
        self.preOrderBottom_re(root.right)           

複制

#3 測試

#2.3 中序周遊

#1 思路

#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 levelOrderBottom(self, root):
        """
        中序周遊 非遞歸
        :param root:  根節點
        :return: list_node -> List
        """
        stack_node = []  # 棧
        list_node = []  # 中序周遊結果存放清單
        node_p = root # 目前節點
        while stack_node or node_p: # 目前節點不為空 or 棧不為空

            while node_p: # 一直移動到最左端
                stack_node.append(node_p) # 節點壓棧
                node_p = node_p.left # 指針左移

            node = stack_node.pop() # 出棧 
            list_node.append(node.val) # 擷取節點資料 
            node_p = node.right # 擷取有節點
        print(list_node)
        return list_node
    
    def inOrderBottom_re(self, root):
        """
        中序周遊 遞歸
        :param root: 根節點
        :return: list_node -> List
        """

        if not root:
            return None
        self.inOrderBottom_re(root.left)
        print(root.val)
        self.inOrderBottom_re(root.right)           

複制

#3 測試

#2.4 後序周遊

#1 思路

#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 levelOrderBottom(self, root):
        """
        後序周遊 非遞歸
        :param root: 根節點
        :return: list_node -> List
        """
        stack_node = [root]
        list_node = []

        while stack_node:
            node = stack_node.pop()

            if node.left: # 左孩子不為空
                stack_node.append(node.left) # 左孩子壓棧
            if node.right: # 右孩子不為空
                stack_node.append(node.right) # 右孩子壓棧

            list_node.append(node.val) # 擷取目前指針數值

        list_node.reverse() # 取反
        return list_node
    
    def postOrderBottom_re(self, root):
        """
        後序周遊 遞歸
        :param root: 根節點
        :return: list_node -> List
        """

        if not root:
            return None
        self.postOrderBottom_re(root.left)
        self.postOrderBottom_re(root.right)
        print(root.val)           

複制

#3 測試