LeetCode-144-二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

image.png
image.png

解题思路：

1. 递归和迭代两种方案；
2. 迭代方案，用栈stack来存储已经遍历过的根节点，当左节点为None时，使用出栈让指针回退到根节点，然后走到右节点，并继续遍历。

Python3代码：

# 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]:
        # 前序遍历 根->左->右
        # 递归方法
        ans = []
        if root:
            ans += [root.val]
            if root.left: 
                ans += self.preorderTraversal(root.left)
            if root.right:
                ans += self.preorderTraversal(root.right)
            return ans
        else:
            return None 

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 迭代方法
        stack = []
        node = root
        res = []
        while stack or node:
            while node:
                res.append(node.val)
                stack.append(node)
                node = node.left
            node = stack.pop()
            node = node.right
        return res