0145. 二叉树的后序遍历 #
- 标签:栈、树
- 难度:简单
题目大意 #
描述:给定一个二叉树的根节点 root
。
要求:返回该二叉树的后序遍历结果。
说明:
- 树中节点数目在范围 $[0, 100]$ 内。
- $-100 \le Node.val \le 100$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:递归遍历 #
二叉树的后序遍历递归实现步骤为:
- 判断二叉树是否为空,为空则直接返回。
- 先递归遍历左子树。
- 然后递归遍历右子树。
- 最后访问根节点。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。其中 $n$ 是二叉树的节点数目。
- 空间复杂度:$O(n)$。
思路 2:模拟栈迭代遍历 #
我们可以使用一个显式栈 stack
来模拟二叉树的后序遍历递归的过程。
与前序、中序遍历不同,在后序遍历中,根节点的访问要放在左右子树访问之后。因此,我们要保证:在左右孩子节点访问结束之前,当前节点不能提前出栈。
我们应该从根节点开始,先将根节点放入栈中,然后依次遍历左子树,不断将当前子树的根节点放入栈中,直到遍历到左子树最左侧的那个节点,从栈中弹出该元素,并判断该元素的右子树是否已经访问完毕,如果访问完毕,则访问该元素。如果未访问完毕,则访问该元素的右子树。
二叉树的后序遍历显式栈实现步骤如下:
- 判断二叉树是否为空,为空则直接返回。
- 初始化维护一个空栈,使用
prev
保存前一个访问的节点,用于确定当前节点的右子树是否访问完毕。 - 当根节点或者栈不为空时,从当前节点开始:
- 如果当前节点有左子树,则不断遍历左子树,并将当前根节点压入栈中。
- 如果当前节点无左子树,则弹出栈顶元素
node
。 - 如果栈顶元素
node
无右子树(即not node.right
)或者右子树已经访问完毕(即node.right == prev
),则访问该元素,然后记录前一节点,并将当前节点标记为空节点。 - 如果栈顶元素有右子树,则将栈顶元素重新压入栈中,继续访问栈顶元素的右子树。
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n)$。其中 $n$ 是二叉树的节点数目。
- 空间复杂度:$O(n)$。