0144. 二叉树的前序遍历 #
- 标签:栈、树
- 难度:中等
题目大意 #
描述:给定一个二叉树的根节点 root
。
要求:返回该二叉树的前序遍历结果。
说明:
- 树中节点数目在范围 $[0, 100]$ 内。
- $-100 \le Node.val \le 100$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:递归遍历 #
二叉树的前序遍历递归实现步骤为:
- 判断二叉树是否为空,为空则直接返回。
- 先访问根节点。
- 然后递归遍历左子树。
- 最后递归遍历右子树。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。其中 $n$ 是二叉树的节点数目。
- 空间复杂度:$O(n)$。
思路 2:模拟栈迭代遍历 #
二叉树的前序遍历递归实现的过程,实际上就是调用系统栈的过程。我们也可以使用一个显式栈 stack
来模拟递归的过程。
前序遍历的顺序为:根节点 - 左子树 - 右子树,而根据栈的「先入后出」特点,所以入栈的顺序应该为:先放入右子树,再放入左子树。这样可以保证最终为前序遍历顺序。
二叉树的前序遍历显式栈实现步骤如下:
- 判断二叉树是否为空,为空则直接返回。
- 初始化维护一个栈,将根节点入栈。
- 当栈不为空时:
- 弹出栈顶元素
node
,并访问该元素。 - 如果
node
的右子树不为空,则将node
的右子树入栈。 - 如果
node
的左子树不为空,则将node
的左子树入栈。
- 弹出栈顶元素
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n)$。其中 $n$ 是二叉树的节点数目。
- 空间复杂度:$O(n)$。