Daily LeetCode 144. Binary Tree Preorder Traversal

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

Medium

问题描述：

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

题目分析：

这条题目是很经典的问题，前序遍历二叉树。

前序遍历思想：根->左->右

根据这种思路，我们能够很容易地写出递归版本，主要来讨论非递归版本：

从root出发，对于任意节点，我们直接访问，再判断该节点是否有左子树，若存在左子树，则执行上述步骤，直到左子树为空。左子树为空时，我们对右子树执行上述操作。为了能够在访问完左子树后继续访问右子树，我们需要一个栈来保存根节点。

访问节点具体步骤：

1. 将该节点入栈，并将当前节点置为左孩子节点
2. 判断当前节点（左孩子节点）是否为空，若为空，取出栈顶节点，将栈顶节点的右孩子节点置为当前节点；否则，重复步骤1，直到左孩子为空或是栈为空。

代码：

递归：

class Solution:
    def preorder_traversal(root):
        res = []
        if root != None:
            res.append(root.val)
            preorder_traversal(root.left)
            preorder_traversal(root.right)
        return res

非递归：

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        current_node = root
        stack = []
        res = []
        while current_node != None or len(stack) != 0:
            if current_node != None:
                stack.append(current_node)
                res.append(current_node.val)
                current_node = current_node.left
            else:
                current_node = stack.pop().right
        return res