二叉树的后序遍历：递归与迭代实现详解 | 深度优先遍历方法

二叉树的后序遍历（Post-order Traversal）是一种深度优先遍历方法，遍历顺序为：左子树 -> 右子树 -> 根节点。这种遍历方式常用于删除树节点或释放树结构，因为它会先处理子节点再处理父节点。

递归实现

递归实现是最直观的方式，代码简洁易懂：

function postOrderTraversal(root) {
  const result = [];
  
  function traverse(node) {
    if (!node) return;
    
    // 遍历左子树
    traverse(node.left);
    // 遍历右子树
    traverse(node.right);
    // 访问根节点
    result.push(node.val);
  }
  
  traverse(root);
  return result;
}

迭代实现

迭代实现需要借助栈来模拟递归调用栈，代码稍复杂但性能更好：

function postOrderTraversal(root) {
  const result = [];
  const stack = [];
  let prev = null; // 记录上一个访问的节点
  
  while (root || stack.length) {
    // 遍历到最左节点
    while (root) {
      stack.push(root);
      root = root.left;
    }
    
    root = stack.pop();
    
    // 如果右子树为空或已经访问过，则访问当前节点
    if (!root.right || root.right === prev) {
      result.push(root.val);
      prev = root;
      root = null; // 避免重复访问
    } else {
      // 否则重新入栈，继续遍历右子树
      stack.push(root);
      root = root.right;
    }
  }
  
  return result;
}

示例

假设有以下二叉树：

    1
   / \
  2   3
 / \   \
4   5   6

后序遍历结果为：[4, 5, 2, 6, 3, 1]。

应用场景

1. 删除二叉树：后序遍历确保子节点先被删除，再删除父节点。
2. 表达式树求值：先计算子表达式，再计算父表达式。
3. 依赖解析：处理依赖关系时，先处理依赖项再处理当前项。

如果你有更多问题或需要进一步优化，请随时告诉我！