前序、中序、後序

前、中、後 的命名由來

若在只有左右子節點的情況下，照慣例順序一定是先執行左、再執行右

當今天加入了parent節點，parent底下會長出左右兩個子節點的情況時
(left代號左、right代號右、parent剛好在左右子節點的中間，所以代號為中)

這個parent節點，相對於左右子節點來說，遍歷的順序要排在最前、中間、還是最後，就有了三種可能，於是分別對應到前序、中序、後序

前序 PreOrder： 中 -> 左 -> 右
中序 InOrder： 左 -> 中 -> 右
後序 PostOrder： 左 -> 右 -> 中

在leetcode上執行

https://leetcode.com/problems/binary-tree-tilt/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        def preOrder(node: TreeNode):
            if node:
                print(node.val) # noed自己的事情最先執行
                preOrder(node.left)
                preOrder(node.right)
        def inOrder(node: TreeNode):
            if node:
                inOrder(node.left)
                print(node.val) # noed自己的事情在left完成後再執行
                inOrder(node.right)
        def postOrder(node: TreeNode):
            if node:
                postOrder(node.left)
                postOrder(node.right)
                print(node.val) # noed自己的事情最後做
        
        print("前序:")
        preOrder(root)
        print()
        
        print("中序:")
        inOrder(root)
        print()
        
        print("後序:")
        postOrder(root)
        print()

[1,2,3,4,5,null,6,7,8,null,null,9,10]

輸出結果:

完整Python程式碼

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


class Object:
    def preOrder(self, node: TreeNode):
        if node:
            print(node.val)  # node自己的事情最先執行
            self.preOrder(node.left)
            self.preOrder(node.right)

    def inOrder(self, node: TreeNode):
        if node:
            self.inOrder(node.left)
            print(node.val)  # node自己的事情在left完成後再執行
            self.inOrder(node.right)

    def postOrder(self, node: TreeNode):
        if node:
            self.postOrder(node.left)
            self.postOrder(node.right)
            print(node.val)  # node自己的事情最後做


# 透過list資料格式來建立TreeNode
# 這種方式保留了每個空元素(None)的位置，與Leetcode在計算Null數量時不一樣
# Leetcode中的Null節點底下不會再留位置
def createBTree(data, index):
    pNode = None
    if index < len(data):
        if data[index] == None:
            return
        pNode = TreeNode(data[index])
        pNode.left = createBTree(data, 2 * index + 1)
        pNode.right = createBTree(data, 2 * index + 2)
    return pNode


l = [1, 2, 3, 4, 5, None, 6, 7, 8, None, None, None, None, 9, 10]
# 等價於Leetcode上的input輸入 [1,2,3,4,5,null,6,7,8,null,null,9,10]

tree = createBTree(l, 0)
obj = Object()
obj.preOrder(tree)

print("前序:")
obj.preOrder(tree)
print()

print("中序:")
obj.inOrder(tree)
print()

print("後序:")
obj.postOrder(tree)
print()