本文共 1090 字，大约阅读时间需要 3 分钟。

二叉树的后序遍历

问题描述

给定一个二叉树，返回它的后序遍历结果。

思路说明

后序遍历是一种常见的树遍历方式，其特点是先遍历左子树，再遍历右子树，最后访问根节点。这种遍历方式在某些应用场景中非常有用，例如在某些计算或累加操作中，先处理叶子节点再处理根节点会更合理。

实现后序遍历的常用方法是使用递归算法。递归的思路非常适合处理树结构，因为每个节点的操作可以独立分解为处理左子树和右子树两个步骤。

实现代码

import java.util.ArrayList;
import java.util.List;
public class BinaryTreePostOrder {
    public List
   
     postOrderTraversal(TreeNode root) {
        List
    
      result = new ArrayList<>();
        postOrder(root, result);
        return result;
    }
    private void postOrder(TreeNode root, List
     
       result) {
        if (root != null) {
            // 处理左子树
            postOrder(root.left, result);
            // 处理右子树
            postOrder(root.right, result);
            // 处理当前节点
            result.add(root.val);
        }
    }
}
     
    
   

代码解释

这种实现方式的时间复杂度是O(n)，其中n是树的节点数。因为每个节点都会被访问一次。

总结

通过递归方法，我们可以轻松实现二叉树的后序遍历。这种方法的时间复杂度是O(n)，空间复杂度是O(n)，其中n是树的节点数。递归算法的思路简单直观，适合处理树结构的各种问题。