# Definition for a binary tree node.
# 前序遍历的意思是先遍历根节点，然后遍历左子树，最后是右子树
# 因此这道题可以用递归的方法直接解出来。
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
from typing import List
class Solution:
    def preorderTraversal1(self, root: TreeNode) -> List[int]:
        self.res = []
        self.dfs(root)
        return self.res
    def dfs(self,root):
        if not root :return
        # 先遍历根节点
        self.res.append(root.val)
        # 然后遍历左子树
        self.dfs(root.left)
        # 然后是右子树
        self.dfs(root.right)
    # 下边是迭代的方法。
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root :return []
        # 将根节点压入栈
        stack,res = [root],[]
        # 当栈为空的时候，代表所有的节点都遍历了
        while stack:
            # 弹出节点
            node = stack.pop()
            # 判断节点是否为空
            if node:
                # 将节点放入列表
                res.append(node.val)
                # 将右节点压入栈
                if node.right :
                    stack.append(node.right)
                # 将左节点压入栈
                if node.left :
                    stack.append(node.left)
        return res