大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定二叉树的根节点，完成后序遍历。”
2、题目描述
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1： 输入： root = [1,null,2,3] 输出： [3,2,1]
示例 2： 输入： root = [1] 输出： [1]
二、解题
1、思路分析
二叉树的后序遍历也讲过很多遍了。
也就是按照左子树→右子树→根节点的方式遍历这棵树。
在访问整个树的时候，也是同样的方式遍历，知道遍历整个树。
遍历过程具有递归性质，可以使用递归函数来模拟这一过程。
2、代码实现
代码参考：
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); postorder(root, res); return res; } public void postorder(TreeNode root, List<Integer> res) { if (root == null) { return; } postorder(root.left, res); postorder(root.right, res); res.add(root.val); } }
3、时间复杂度
时间复杂度：O(n)
其中n是二叉树的节点数，每个节点会被访问一次。
空间复杂度：O(n)
其中n是二叉树的节点数，主要是递归过程在栈上的开销。
三、总结
首先实现一个递归函数来遍历整个树。
在递归调用的时候，先将左子树传入，遍历左子树，然后将右子树传入，遍历右子树。
最后将root节点的值加入答案即可。
遍历终止条件为碰到空节点
