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

前言

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

围观我刷题的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官方有一种很巧妙的解法，在这里分享给大家。