# Binary Tree Traversal (二元樹追蹤)
**keywords**: binary search trees (BST), recursive

### Depth-First Traversals (DFT)
看到D就**印出**/**處理**資料

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

#### 1. Preorder (<font color="#f00">D</font>LR)
虛擬碼

Procedure preOrder(T: Pointer to B.T. root): // 指向某樹的root
    if(T is not null): // 樹不是空的狀況
        print(T->data) // D
        preOrder(T->leftSubtree) // L
        preOrder(T->rightSubtree) // R
    endif
    
    return
end preOrder

python實作

def printPreorder(root):
    # DLR
    if root:
        print(root.data)
        printPreorder(root.left)
        printPreorder(root.right)
    return

#### 2. Inorder (L<font color="#f00">D</font>R)
虛擬碼

Procedure inOrder(T: Pointer to B.T. root): // 指向某樹的root
    if(T is not null): // 樹不是空的狀況
        inOrder(T->leftSubtree) // L
        print(T->data) // D
        inOrder(T->rightSubtree) // R
    endif
    
    return
end preOrder

python實作

def printInorder(root):
    # LDR
    if root:
        printInorder(root.left)
        print(root.data)
        printInorder(root.right)
    return

#### 3. Postorder (LR<font color="#f00">D</font>)
虛擬碼

Procedure postOrder(T: Pointer to B.T. root): // 指向某樹的root
    if(T is not null): // 樹不是空的狀況
        postOrder(T->leftSubtree) // L
        postOrder(T->rightSubtree) // R
        print(T->data) // D
    endif
    
    return
end preOrder

python實作

def printPostorder(root):
    # LRD
    if root:
        printPostorder(root.left)
        printPostorder(root.right)
        print(root.data)
    return

以下圖這棵樹為例

if __name__ == '__main__':
    root = Node('A') 
    root.left = Node('B') 
    root.right = Node('E') 
    root.left.left = Node('C') 
    root.left.right = Node('D')
    root.right.right = Node('F')

    printInorder(root)
    # C B D A E F

    printPreorder(root)
    # A B C D E F

    printPostorder(root)
    # C D B F E A

### Leetcode實戰

# 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

- [x] [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)
- **Recursive**

"""
        A
      /   \ 
     B     E
    / \      \
   C   D      F
""" 
class Solution:
    def inorderTraversal(self, root):
        # LDR
        result = []
        if root:
            # Q:為何是+=不是append? A:詳見最下方Appendix
            result += self.inorderTraversal(root.left) # L 
            result.append(root.val) # D
            result += self.inorderTraversal(root.right) # R
        return result

- **Iterative**: use stack
想法:Inorder是L -> D -> R的順序。
1. 先跑L然後push進stack，一直到L.left為None就pop出L.data
2. 再跑stack最上層的L.right
就醬，心領神會一下。

"""
        A
      /   \ 
     B     E
    / \      \
   C   D      F
stack []
result [C, B, D, A, E, F]
root = None
"""   
class Solution:
    def inorderTraversal(self, root):
        stack = []
        result = [] 
        while root is not None or stack != []:
            while root is not None:
                stack.append(root)
                root = root.left #L
            root = stack.pop()
            result.append(root.val) #D
            root = root.right # R
        return result

- [x] [144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)
- **Recursive**

class Solution:    
    def preorderTraversal(self, root):
        # DLR
        result = []
        if root:
            result.append(root.val) # D
            result += self.preorderTraversal(root.left) # L
            result += self.preorderTraversal(root.right) # R
        return result

- **Iterative**

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        result = []
        while root or stack != []:
            while root:
                stack.append(root)
                result.append(root.val) # D
                root = root.left #L
            root = stack.pop()
            root = root.right # R
        return result

解法2

"""
Preorder: root -> left -> right
想法: 用stack存值，而stack是後進先出所以先存right再存left
stack先放root
當stack不為空的時候:
    result存root.val
    如果root.right有值:
        stack存root.right
    如果root.left:
        stack存root.left
        
        A
      /   \ 
     B     E
    / \      \
   C   D      F
step1:
    result: [A]
    stack: [E, B]
    stack: [E]
    root = B
step2:
    result: [A, B]
    stack: [E, D, C]
    stack: [E, D]
    root = C
step3:
    result: [A, B, C]
    stack: [E]
    root = D
step4:
    result: [A, B, C, D]
    stack: []
    root = E
step5:
    result: [A, B, C, D, E]
    stack: [F]
    stack: []
    root = F
step6:
    result: [A, B, C, D, E, F]
    break while
"""
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        
        result = []
        stack = [root] #先把root放進去
        
        while stack != []:
            root = stack.pop()
            result.append(root.val)
            if root.right:
                stack.append(root.right)
            if root.left:
                stack.append(root.left)
            
        return result

- [x] [145. Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)

class Solution:    
    def postorderTraversal(self, root):
        # LRD
        result = []
        if root:
            result += self.postorderTraversal(root.left) # L
            result += self.postorderTraversal(root.right) # R
            result.append(root.val) # D
        return result

if __name__ == '__main__':      
    root = TreeNode('A') 
    root.left = TreeNode('B') 
    root.right = TreeNode('E') 
    root.left.left = TreeNode('C') 
    root.left.right = TreeNode('D')
    root.right.right = TreeNode('F')
    solution = Solution() # 要記得instantiation
    
    print(solution.inorderTraversal(root))
    # ['C', 'B', 'D', 'A', 'E', 'F']
    
    print(solution.preorderTraversal(root))
    # ['A', 'B', 'C', 'D', 'E', 'F']
    
    print(solution.postorderTraversal(root))
    # ['C', 'D', 'B', 'F', 'E', 'A']

- [x] [98. Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)

# 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 isValidBST(self, root: TreeNode) -> bool:
        tree = self.inorderTraversal(root)
        for i in range(len(tree) - 1):
            if tree[i] >= tree[i + 1]:
                return False
        return True
        
    def inorderTraversal(self, root):
        # LDR
        result = []
        if root:
            result += self.inorderTraversal(root.left) # L 
            result.append(root.val) # D
            result += self.inorderTraversal(root.right) # R
        return result

### Reference
1. [Tree Traversals (Inorder, Preorder and Postorder)](https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/)
2. [Ch.06: Tree and Binary Tree (04)](https://www.youtube.com/watch?v=e9zMOPY_6hQ)
### Appendix

a = [1, 2, 3]
b = [4, 5, 6]
a += b
print(a)
# [1, 2, 3, 4, 5, 6]

a = [1, 2, 3]
b = [4, 5, 6]
# list1 append list2的時候，list2會被當成單一個element加到list1裡面
a.append(b) 
print(a)
# [1, 2, 3, [4, 5, 6]]