回顾
上一期我们做的“LeetCode 144. 二叉树的前序遍历”的解法一，有网友问道为什么我们可以把存结果的整数列表res放到辅助的 traverse()递归函数中，逐步将每一步的结果填充入其中呢？
其实，笔记哥上一次分享的文章《10 张 GIF 动图让你弄懂递归等概念》中的“GIF 7：按值传递和按引用传递的区别”解释了这个问题。
在 Java 语言中，int,float,char,double等等是 primitive type，中文貌似翻译做“原始型”，这些类型的数据就是按照数值传递的，所以当这些类型的变量被传进一个函数的时候，内存中的栈(stack)复制了一份它的数值，两个“它们”其实是完全不同的拷贝；当在函数中的它被改值的时候，外面的那个它是不会感应到值的变化的，即这个动图中的“pass by value”☕️ 杯的例子。OK，我们上一期做题的时候，传给traverse()函数的是一个整数列表(List
再次的，解题“七步走” (面试答题时候不一定每一步都用上，但要保持这种 sense)：
- 题意 Scenario
- 假设 Assumptions
- 举例与输入输出 Examples and figure out Input/Output
- 思路（什么数据结构， 什么算法）Thinking Process (What data structure, algorithm?)
- 代码 Coding
- 复杂度分析 Complexity Analysis
- 测试 Tests
题目要求
原题链接
中译：通过后序遍历的方式遍历一个二叉树，并把遍历的每一个节点的值存到一个数组（或整数列表，如果使用的是 Java 语言）中，返回这个数组。
举例与输入输出
如下图所示，第一层根节点有有一个根为 4，根的左节点为 null，右节点为 9。在第二层节点 9 之下，它有左节点为 7，右节点为 null。在图中，我用#号来表示 null。
4
/ \
# 9
/ \
7 #
/ \
# #
那么，我们要得到的结果就应是数组[7, 9, 4]。
思路 1: 从 postorder 的定义出发的方法
postorder 的定义用中文概括就是按 “左右根” 的顺序进行访问。欢迎读者按照上一期“LeetCode 144. 二叉树的前序遍历”的 思路 1 的思考过程，在草稿纸上画一下这棵树的后序遍历访问过程。
代码 1
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// 生成存放结果的整数列表
List<Integer> res = new ArrayList<>();
// 把整数列表放到辅助的traverse()递归函数中，逐步将其填充入结果
traverse(root, res);
// 返回结果整数列表
return res;
}
void traverse(TreeNode root, List<Integer> res) {
// 递归的基本情况: 当根为null的时候
if (root == null) {
return;
}
// 递归的recursive情况: 从postorder定义出发
traverse(root.left, res); // 处理当前root的左子树
traverse(root.right, res); // 处理当前root的右子树
res.add(root.val); // 添加当前root的值进入到结果列表
}
}
思路 2: 分治法
欢迎读者模仿上一期“LeetCode 144. 二叉树的前序遍历”的 思路 2 的思考过程，想一想这棵树的后序遍历访问过程。
您可以思考一下：这一次，节点 7 是不是我们最先处理好的节点？如果是的话，为什么这一次它会在结果数组中出现在第一位呢？
OK，再次回顾一下我们在 LeetCode 226. Invert Binary Tree 这道题的讲解中的分治法模板。
模板：
public TreeNode someFunction(TreeNode root) {
1. write base case
2. write division，conceptually as below:
root.left = someFunction(root.right);
root.right = someFunction(root.left);
3. Conquer
ie. combine some results
return value;
}
经模板推倒出如下代码
代码 2
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// 生成存放结果的整数列表
List<Integer> res = new ArrayList<>();
// base case
if (root == null) {
return res;
}
// write division
List<Integer> left = postorderTraversal(root.left);
List<Integer> right = postorderTraversal(root.right);
// conquer
// conquer的前提是假定当前根的左子树、右子树都搞定了，
// 就按 左右根 的顺序把结果合并起来就行了，符合postorder定义
res.addAll(left);
res.addAll(right);
res.add(root.val);
// 返回结果整数列表
return res;
}
}
代码小结
- 回答 👆 的思考问题。节点 7 确实是我们最先处理好的节点。这一次，在后序遍历的分治解法中，它会在结果数组中出现在第一位，是因为分治解法的治(conquer)的过程保证了输出结果的顺序。 我们看看程序运行到存储以 9 为全局的根的子树时候的情况
res.addAll(left); // 结果列表加入 7
res.addAll(right); // 结果列表加入 空列表，原因是9的右子树为空
res.add(root.val); // 结果列表加入 9
时间与空间复杂度分析
时间复杂度，由于二叉树的每一个节点都会遍历到，所以是O(n)，n 为二叉树的节点个数。
空间复杂度，由于新开了一个变量用于存所有节点的值的res，所以空间复杂度为O(n)。