二叉树后序遍历：三大隐藏绝技，让你的算法功力突飞猛进！

如果你还在死记硬背“左-右-根”的递归代码，那你就错过了后序遍历的真正威力

先看一道经典面试题

“给定一棵二叉树，如何仅使用后序遍历，就能同时解决多个问题？”许多程序员的第一反应是递归，但真正的高手会告知你：后序遍历的本质，是一次精心编排的倒推过程。

今天我要分享的，不是教科书上的基础代码，而是能让你的算法功力立即提升一个档位的三个实战技巧。

技巧一：后序位置——收集信息的黄金位置

后序位置的神奇之处在于：当你站在一个节点上时，你不仅知道自己，还知道它的左右子树的一切信息。

def post_order_traversal(root):
    if not root:
        return 0, True  # 高度，是否平衡
    left_height, left_balanced = post_order_traversal(root.left)
    right_height, right_balanced = post_order_traversal(root.right)
    # 后序位置：此时已获得左右子树的全部信息
    current_height = max(left_height, right_height) + 1
    is_balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1
    return current_height, is_balanced

这个技巧的精髓：许多树形DP问题天然适合在后序位置解决，由于这里可以自底向上地整合信息。

技巧二：迭代后序遍历——理解栈的完美舞蹈

递归虽美，但面试官常问：“能用迭代实现吗？”迭代后序遍历是三种遍历中最巧妙的：

def post_order_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    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]  # 反转后得到真正的后序

这里面的精髓：利用“根-右-左”的遍历顺序，再反转得到“左-右-根”。这种思路也适用于许多需要逆向思维的问题。

技巧三：后序的隐藏模式——从叶子到根的决策链

后序遍历最强劲的应用，是解决那些需要子节点决策才能决定父节点决策的问题。

实战场景：计算二叉树中最大路径和

def max_path_sum(root):
    max_sum = float('-inf')
    def dfs(node):
        nonlocal max_sum
        if not node:
            return 0
        # 后序遍历：先获取左右子树的信息
        left_gain = max(dfs(node.left), 0)
        right_gain = max(dfs(node.right), 0)
        # 在后序位置计算当前节点的贡献
        price_newpath = node.val + left_gain + right_gain
        max_sum = max(max_sum, price_newpath)
        # 返回当前节点能给父节点提供的最大贡献
        return node.val + max(left_gain, right_gain)
    dfs(root)
    return max_sum

这个例子揭示的核心思想：后序遍历让每个节点都能基于子节点的计算结果，做出对自己和父节点最有利的决策。

为什么高手都爱后序遍历？

信息完整性：在后序位置，你掌握了当前节点及其所有后代的信息

决策最优性：适合解决需要自底向上推导最优解的问题

资源释放：在二叉树释放内存、关闭连接等场景中，必须先处理子节点再处理父节点

一个思维框架，解决一类问题

下次遇到二叉树问题，先问自己三个问题：

是否需要先知道子树的结果才能决定当前节点？

是否需要从叶子到根的推导顺序？

是否涉及子树信息的整合？

如果有一个答案是“是”，那么后序遍历很可能就是最佳解决方案。

记住这个模式：许多复杂的二叉树问题，本质上都是后序遍历的变体。掌握了这种思维方式，你会发现原来需要苦思冥想的问题，目前都有了清晰的解决路径。

算法不是死记硬背，而是理解本质后的灵活运用。 后序遍历教给我们的，不仅仅是一种遍历顺序，更是一种自底向上、整合信息、优化决策的思维方式。

你目前是否已经想到了曾经遇到的某个问题，实则可以用后序遍历的思路更优雅地解决？在评论区分享你的发现吧！

彩蛋：

1.介绍

二叉树的后序遍历是一种遍历二叉树的策略，按照”左子树-》右子树-》根节点”的顺序访问节点的子树或根节点。具体来说，后序遍历第一访问左子树，然后访问右子树，最后访问根节点。

这种遍历方式在编程中可以通过递归或非递归的方式进行实现。

一般来说，递归算法较容易理解，但可能会造成栈溢出，而非递归算法较难理解。

以下用代码实现后序遍历。

2.代码

以下以Java编程语言为例。

1）二叉树节点的数据结构定义如下：

classTreeNode {
intvalue;
    TreeNode left;
    TreeNode right;
    TreeNode(intvalue) {
      this.value = value;
    }
}

2）后序遍历递归算法代码

public void postOrderTraversalRecursive(TreeNode root){
//若root节点为空，则子遍历完成
    if(null==root){
        return ;
     }
//先递归遍历左子树
        postOrderTraversalRecursive(root.left);
//再递归遍历右子树
        postOrderTraversalRecursive(root.right);
//最后访问根节点
        System.out.println(root.value);
}

3）后序遍历非递归算法代码（单栈法）

可以使用栈来模拟递归过程。此例只用到了一个栈，所以叫做单栈法。

后序遍历与前序遍历和中序遍历存在差异。即我们在访问左子树之后需要访问右子树，然后才能再访问根节点，所以我们的根节点不能在访问左子树之后出栈，而是需要继续访问右子树，当我们右子树访问完成之后再出栈。

public void postOrderTraversalNonRecursive(TreeNode root)
{
//存储遍历过程中的需要继续处理的临时节点
    Stack<TreeNode> stack = new Stack<>();
//保存临时根节点，从root开始
    TreeNode node =root;
//保存上次访问的节点，从root开始
    TreeNode lastVisit = root;
//临时节点不为空或者栈不为空时需要继续处理
    while(null != node || !stack.empty())
    {
        while(null != node){
//存储临时节点到栈中
            stack.push(node);
//继续遍历左子树
            node = node.left;
        }
//查看当前栈顶元素
        node = stack.peek();
//如果当前栈顶元素的右子树为空，或者右子树已经被访问，则说明左右节点都访问完成了
//则可以直接输出当前节点的值
       if(null == node.right || node.right==lastVisit){
//左子树与右子树都访问完成后输出当前根节点的值
            System.out.println(node.value+" ");
//当前节点已处理完成，从栈中弹出，继续下一轮遍历
            stack.pop();
//更新上次访问的节点
            lastVisit=node;
//左子树右子树根节点都访问完毕后，将临时节点置空，从而从栈中处理下一个节点
            node=null;
        }else{
//右子树尚未被访问，则继续遍历右子树
            node=node.right;
        }
    }
}

4）后序遍历非递归算法代码（双栈法）

由于后序遍历的输出顺序是左->右->根，倒过来就是根->右->左。因此利用栈（先进后出FILO，与正常顺序是反的）的性质，只需要按照根->右->左的访问顺序访问一次，并存入栈中，最后从栈顶输出所有栈节点就可以了。

算法需要两个栈，一个是正常遍历需要的栈，一个是存储倒过来的元素的栈，所以也叫双栈法。

public static void postOrderTraversalNonRecursive2Stack(TreeNode root) {
//后序遍历中存储正常访问顺序的栈
   Stack<TreeNode> stack = new Stack<TreeNode>();
//后序遍历中存储逆向访问顺序的栈
   Stack<TreeNode> output = new Stack<TreeNode>();
   TreeNode node = root;
//判断是否还有节点需要处理
   while (null != node || !stack.isEmpty()) {
       if (null != node) {
//先访问根节点，压入栈中
         stack.push(node);
         output.push(node);
//再访问右子节点
         node = node.right;
       } else {
//再访问左子节点
         node = stack.pop();
         node = node.left;
     }
   }




//从栈顶开始输出栈里元素的值，即输出正常访问顺序栈stack的倒序结果output栈，即为最终结果
   while (output.size() > 0) {
     TreeNode n = output.pop();
     System.out.print(n.value + " ");
   }
}

5）后序遍历非递归算法代码（Stack+Deque，即栈+双向队列法）

算法的数据结构里，一个存储正常遍历需要的栈，一个存储最终输出的元素双端队列列表，所以也叫栈+双向队列法。

public List<TreeNode> postOrderTraversalNonRecursiveStackDeque(TreeNode root) {
//保存计算出的最终结果列表
   LinkedList<TreeNode> result = new LinkedList<>();
//若root节点为空，则遍历完成
   if (null == root) {
     return result;
   }
//后序遍历中存储正常访问顺序的栈
   Stack<TreeNode> stack = new Stack<>();
//压入根节点到栈中
   stack.push(root);
//存储当前节点
   TreeNode curNode;
//若栈中有数据，则继续处理
   while(!stack.isEmpty()) {
//获取当前栈顶元素
     curNode = stack.pop();
//将栈顶元素插入到结果列表LinkedList的头部
     result.addFirst(curNode.value);
     if (null != curNode.left) {
//压入左子节点到栈中
        stack.push(curNode.left);
     }
     if (null != curNode.right) {
//压入右子节点到栈中
        stack.push(curNode.right);
     }
   }
   return result;
}