二叉树的后序遍历 | ｜Java 开发实战

【话不多说】

leecode 145. 二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]

输出: [3,2,1]

首先我们需要了解什么是二叉树的后序遍历：按照访问左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

参考代码

定义一颗树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int          // 根
 *     Left *TreeNode   //左节点
 *     Right *TreeNode  //右节点
 * }
 */
复制代码

1. 直接怼到最下面的左节点，如果为null,走postorder(node.Right),如果在右节点还有左节点就继续走左节点，直到到最下面的左节点，走第三步，将左节点怼进数组里。

2. return到右节点，怼进数组

3. 将根节点怼进数组。

GO语言版 递归

func postorderTraversal(root *TreeNode) (res []int) {
    var postorder func(*TreeNode)
    postorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        postorder(node.Left)  //  1
        postorder(node.Right)  // 2
        res = append(res, node.Val)  // 3
    }
    postorder(root)
    return
}



复制代码

GO语言版 迭代 栈：先进后出

定义一个栈stk，栈存的就是一棵树

1.先将根节点怼进数组,遍历把左子树全部怼进栈，知道最下面的左节点。

2.将最后进入栈的节点弹出来

3.弹出的节点，如果左节点不为空或者右节点不为空，就继续入栈

4.如果为空，说明这个根节点就是左节点或者右节点，因为左节点先出栈，所以把左节点怼进数组，在怼右节点，直到最后一个根节点。

func postorderTraversal(root *TreeNode) (res []int) {
    stk := []*TreeNode{} 
    var prev *TreeNode
    for root != nil || len(stk) > 0 {
        for root != nil {
            stk = append(stk, root)  // 1.
            root = root.Left
        }
        root = stk[len(stk)-1]
        stk = stk[:len(stk)-1] // 2.
        if root.Right == nil || root.Right == prev { // 3.
            res = append(res, root.Val) // 4. 
            prev = root
            root = nil
        } else {
            stk = append(stk, root)
            root = root.Right
        }
    }
    return
}


复制代码