LeetCode 题解工作台
二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。 示例 1： 输入： root = [1,null,2,3] 输出： [3,2,1] 解释： 示例 2： 输入： root = [1,2,3,4,5,null,8,null,null,6,7,9] 输出： [4,6,7,5,2,9,8,…
4
题型
6
代码语言
3
相关题
当前训练重点
简单 · 二分·树·traversal
答案摘要
我们先递归左右子树，然后再访问根节点。 时间复杂度 ，空间复杂度 。其中 是二叉树的节点数，空间复杂度主要取决于递归调用的栈空间。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
解题思路
方法一：递归
我们先递归左右子树，然后再访问根节点。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数，空间复杂度主要取决于递归调用的栈空间。
# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(root):
if root is None:
return
dfs(root.left)
dfs(root.right)
ans.append(root.val)
ans = []
dfs(root)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
A correct solution requires tracking the traversal state to avoid revisiting nodes.
- question_mark
Look for the candidate’s ability to optimize space usage with stack-based solutions.
- question_mark
Candidates should be able to describe postorder traversal in detail, including why root is visited last.
常见陷阱
外企场景- error
Failing to properly manage the stack and state tracking may lead to incorrect results.
- error
Misunderstanding the traversal order can result in an incorrect sequence, especially when reversing the stack output.
- error
Forgetting edge cases, like empty trees, where the result should be an empty list.
进阶变体
外企场景- arrow_right_alt
Using a recursive approach instead of a stack-based solution.
- arrow_right_alt
Adding constraints to the problem, such as limiting the tree depth or node values.
- arrow_right_alt
Modifying the traversal order, such as pre-order or in-order traversal, to test flexibility with different traversal strategies.