Binary Tree & Preorder Traversal

Binary Tree(二叉樹)是一種樹形結構，每個節點最多只有兩個子節點(左節點和右節點)的linkedlist。Binary Tree中每個節點都包含一個值和一個指向左節點和右節點的指針。

Binary Tree的算法是先序遍歷，從root node開始，先輸出root node，然後遍歷左子樹，最後遍歷右子樹。具體步驟如下：

當變數有指到node的情況下

盡量往左走
走到的先拜訪 (你要做的事)

當變數沒有指到node

判斷是不是走不下去，若走不下去往上找可以的parent.right回到root node

以下code可以帶入各種Binary Tree的題目，其中root表示Binary Tree的根節點，stack是一個堆疊，用來暫存未處理的節點。程式碼首先將根節點入堆疊，然後遍歷其左子樹直到左子樹的末端，期間遇到的所有節點都加入堆疊。當左子樹處理完成後，程式碼從堆疊中取出節點，遍歷其右子樹。這樣依次處理所有節點，就完成了二叉樹的前序遍歷。


root = Tree()

stack = []
while stack or root:
    if root:
        print(root.val) # visit
        stack.append(root)
        root = root.left
    else:
        root = stack.pop()
        root = root.right

以下是用preorder的方法去解leetcode的Binary Tree