前序遍历

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/submissions/

思路用一个栈，root进入栈后就直接输出，并把左右子树加进去，因为是栈，所以要先加右子树再加左子树，这样保证出栈的时候是左子树先出。
如果是队列实现，可以用先append左子树，再append右子树

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        arr = []
        if not root:
            return arr
        stack = [root]
        while stack:
            tmp = stack.pop()
            arr.append(tmp.val)
            # 注意这里是栈，所以先把右子树push进去，后把左子树push进去，这样出栈的时候就是左先出来
            if tmp.right:
                stack.append(tmp.right)
            if tmp.left:
                stack.append(tmp.left)
             
        return arr