难度: Easy
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[3,2,1]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
Submission
运行时间: 44 ms
内存: 14.9 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 postorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
Explain
这个题解使用了迭代的方式实现二叉树的后序遍历。具体思路如下： 1. 如果根节点为空，直接返回空列表。 2. 初始化一个栈，并将根节点压入栈中。 3. 初始化一个结果列表 `result`，用于存储后序遍历的节点值。 4. 当栈不为空时，循环执行以下操作： - 弹出栈顶节点，并将其值追加到结果列表 `result` 的尾部。 - 如果该节点有左子节点，将左子节点压入栈中。 - 如果该节点有右子节点，将右子节点压入栈中。 5. 由于后序遍历的顺序是左-右-根，而我们在将节点值追加到结果列表时，顺序是根-右-左，因此需要将结果列表反转后返回。
时间复杂度: 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 postorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
stack = [root] # 初始化栈，并将根节点压入栈中
result = [] # 初始化结果列表
while stack:
node = stack.pop() # 弹出栈顶节点
result.append(node.val) # 将节点值追加到结果列表的尾部
if node.left: # 如果节点有左子节点
stack.append(node.left) # 将左子节点压入栈中
if node.right: # 如果节点有右子节点
stack.append(node.right) # 将右子节点压入栈中
return result[::-1] # 反转结果列表并返回
Explore
在迭代方法中，直接遵循后序遍历的左-右-根顺序较为复杂，因为需要在遍历过程中不断地检查节点是否已经被访问过。通过先将根节点值加入结果列表，再按根-右-左的顺序处理子节点，我们可以利用栈的后进先出特性来简化这一过程。这种处理方式允许我们不用标记节点的访问状态，从而简化代码。最后通过反转列表，使得结果符合后序遍历的左-右-根顺序。
在迭代实现中，顺序非常关键，因为我们最终需要的输出顺序是左-右-根。首先处理根节点，然后将右子节点压入栈，接着压入左子节点。这样做是为了确保左子节点在栈中位于右子节点之上，以便它能在右子节点之前被处理和弹出。这个顺序是反向处理的，因为栈是一种后进先出的数据结构。
使用迭代方法并在最后反转结果列表的主要优势是简化了操作逻辑和实现复杂度。如果尝试直接在迭代过程中按照后序遍历的顺序添加结果，我们需要频繁地检查每个节点是否已经处理过其子节点，这通常需要额外的数据结构如哈希表来记录这些信息。通过先根-右-左的顺序添加，然后简单地反转列表，我们避免了这种复杂性，并利用了栈这一数据结构的天然属性。
迭代方法的优势在于它通常使用显式的栈来控制调用过程，这可以避免递归带来的栈溢出的风险，尤其是在处理深度很大的树时。此外，迭代方法的空间复杂度更易于控制。然而，迭代的劣势在于实现上通常比递归复杂，可读性和维护性可能较差。递归方法的代码更加直观和简洁，特别是对于树这种天然具有递归结构的数据结构。