前言
最近一直在刷题，但解析题目的文章远远落后了。毕竟写文档对于程序员来说，不是一件容易的事情。
围观我刷题的Github地址:https://github.com/JohnTsaiAndroid/KotlinLeetCode
欢迎各位star，watch，fork(素质三连
题目
145. 二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解法
- 递归法
首先复习下，树和二叉树的相关知识。
树：是一种数据结构，由n（n>0）个有限节点组成一个具有层次关系的集合。它看起来像一棵倒挂的树，所以叫做树。
二叉树：是每个节点最多只有两个分支的树结构
然后我们了解下：什么是二叉树的后序遍历
后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。
同理，根据根节点的访问先后不同，依此还有前序遍历和中序遍历。
image.png
由于树这种数据结构的特殊性，我们一般首先会想到使用递归法来解决树相关的问题。
伪代码如下
if root 为空
return
后序遍历(root.left) //以左子节点为根节点后序遍历
后序遍历(root.right) //以右子节点为根节点后序遍历
root.val //输出根节点
import java.util.*
/*
* Created by johntsai on 2019-07-27
*/
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun postorderTraversal(root: TreeNode?): List<Int> {
if (root == null) {
return Collections.emptyList()
}
val result = ArrayList<Int>()
result.addAll(postorderTraversal(root.left))
result.addAll(postorderTraversal(root.right))
result.add(root.`val`)
return result
}
}
- 迭代法
由于后序遍历的特殊性，因此迭代法实现并不是很好理解。
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-hou-xu-bian-li-by-leetcode/
Leetcode官方有一种很巧妙的解法，在这里分享给大家。
