难度: Easy
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,2,3]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[1,2]
示例 5：
输入：root = [1,null,2] 输出：[1,2]
提示：
[0, 100] 内-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
运行时间: 40 ms
内存: 14.8 MB
# 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]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
这个题解使用迭代的方式实现了二叉树的前序遍历。具体思路如下： 1. 如果根节点为空，直接返回空列表 []。 2. 创建一个栈 stack，初始时将根节点压入栈中。 3. 创建一个结果列表 result，用于存储前序遍历的结果。 4. 当栈不为空时，循环执行以下步骤： - 从栈顶弹出一个节点 node。 - 将 node 的值加入结果列表 result。 - 如果 node 的右子节点不为空，将右子节点压入栈中。 - 如果 node 的左子节点不为空，将左子节点压入栈中。 5. 返回结果列表 result，即为二叉树的前序遍历结果。
时间复杂度: O(n)
空间复杂度: O(n)
# 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]
# 创建一个结果列表，用于存储前序遍历的结果
result = []
# 当栈不为空时，循环执行以下步骤
while stack:
# 从栈顶弹出一个节点
node = stack.pop()
# 将节点的值加入结果列表
result.append(node.val)
# 如果节点的右子节点不为空，将右子节点压入栈中
if node.right:
stack.append(node.right)
# 如果节点的左子节点不为空，将左子节点压入栈中
if node.left:
stack.append(node.left)
# 返回前序遍历的结果列表
return result
在迭代方法中，先将右子节点压入栈然后是左子节点的顺序是为了保证左子节点先被处理。栈是一种后进先出（LIFO）的数据结构，因此最后进栈的元素会最先被访问。在前序遍历中，我们需要按照根-左-右的顺序访问节点。如果我们先将左子节点压入栈，由于栈的这种特性，左子节点会在右子节点之前被弹出并访问，从而满足前序遍历的要求。
在这个迭代版本的前序遍历中，由于左子节点最后被压入栈并因此最先被访问，该实现正确地遵守了标准的根-左-右访问顺序。只要栈的操作顺序保持一致（即总是先压入右子节点，再压入左子节点），就不会出现不遵循标准访问顺序的情况。
栈结构在这个算法中起到了将访问的节点暂存并控制访问顺序的作用，确保了前序遍历的正确顺序（根-左-右）。如果使用队列代替栈，由于队列是先进先出（FIFO）的数据结构，节点将按照它们被添加到队列的顺序被访问，这将改变节点的访问顺序。具体来说，如果我们仍然按照‘先右后左’的顺序添加子节点到队列，将得到层序遍历的结果，而不是前序遍历。
在这个迭代前序遍历的实现中，每个节点确实最多只被访问一次，因为每个节点在从栈中弹出时会立即被处理（访问其值并探索其子节点），然后不会再被压回栈中。在一些其他的树遍历算法中，如非递归的中序遍历，节点可能在达到左子树的最底部后再次被访问，以便回溯到其右子树。