DFS template:

Divided & Conquer template：

这个思想特别重要，适用于大多数的Tree问题。

preorder traversal:

root-left-right

iterative:

def preorder(root):
    def traversal(root, res):
        if not root: return 
        res.append(root.val)
        traversal(root.left)
    res = []
    traversal(root, res)
    return res

divide & conquer

inorder traversal:

postorder traversal: