每日一题20201208（144. 二叉树的前序遍历）

144. 二叉树的前序遍历

递归写法

前序遍历顺序就是 根节点->左节点->右节点

# 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 preorderTraversal(self, root: TreeNode) -> List[int]:
        node = []
        self.order(root, node)
        return node

    def order(self, root, node):
        if root is None:
            return
        node.append(root.val)
        self.order(root.left, node)
        self.order(root.right, node)

迭代写法

通过一个栈来维护节点的输出顺序，每次出一个节点，把节点的值拿出来放到结果数组里，请注意栈是先进后出。

所以先进right节点，到时候先出的就是left节点。

# 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 preorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        stack = [root]
        ans = []
        while len(stack) > 0:
            current = stack.pop()
            ans.append(current.val)
            if current.right is not None:
                stack.append(current.right)
            if current.left is not None:
                stack.append(current.left)
        return ans