每天一道LeetCode题——二叉树的后序遍历每天一道LeetCode题——二叉树的

前言
最近一直在刷题，但解析题目的文章远远落后了。毕竟写文档对于程序员来说，不是一件容易的事情。

文章图片

围观我刷题的Github地址:https://github.com/JohnTsaiAndroid/KotlinLeetCode
欢迎各位star，watch，fork(~~素质三连~~

题目
【每天一道LeetCode题——二叉树的后序遍历】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 {if (root == null) { return Collections.emptyList() }val result = ArrayList() 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官方有一种很巧妙的解法，在这里分享给大家。