145. 二叉树的后序遍历

leecode原题

题目

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例

示例 1:

输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2:

输入：root = []
输出：[]

示例 3:

输入：root = [1]
输出：[1]

提示：

• 树中节点的数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

解题思路

思路

递归实现

递归实现是比较简单的，记住左子树->右子树->根节点的遍历顺序即可，另外要当心golang里面切片传递的坑！

迭代实现

借用栈搞定，其实也简单，详见代码，有详细步骤。

实现

源码
递归实现

func postorderTraversal(root *TreeNode) []int {
    nodeArr := make([]int, 0)
    traversal(root, &nodeArr)
    return nodeArr
}

func traversal(cur_node *TreeNode, arr *[]int) {
    if cur_node == nil {
        return
    }
    traversal(cur_node.Left, arr)
    traversal(cur_node.Right, arr)
    *arr = append(*arr, cur_node.Val)
}

迭代实现

// 用数据实现一个基本功能的栈
type Stack struct {
    elements []*TreeNode
}

func NewStack() *Stack {
    return &Stack{elements: make([]*TreeNode, 0)}
}

func (s *Stack) IsEmpty() bool {
    if len(s.elements) == 0 {
        return true
    }
    return false
}

func (s *Stack) Push(element *TreeNode) {
    s.elements = append(s.elements, element)
}

func (s *Stack) Pop() *TreeNode {
    if !s.IsEmpty() {
        res := s.elements[len(s.elements)-1]
        s.elements = s.elements[:len(s.elements)-1]
        return res
    }
    return nil
}

// 迭代遍历
func postorderTraversal(root *TreeNode) []int {
    nodeArr := make([]int, 0)
    if root == nil {
        return nodeArr
    }
    // 普通栈
    s := NewStack()
    // 输出栈
    out := NewStack()
    // 步骤1: 直到当前结点为空 & 栈空时，循环结束
    for root != nil || !s.IsEmpty() {
        // 步骤2: 判断当前结点是否为空
        if root != nil {
            // 步骤3: 将当前节点输入到普通栈和输出栈
            s.Push(root)
            out.Push(root)
            // 步骤4: 置当前结点的右孩子为当前节点
            root = root.Right
            // 返回步骤1
        } else {
            // 步骤5：出栈栈顶结点
            root = s.Pop()
            // 步骤6：置当前结点的左孩子为当前节点
            root = root.Left
            // 返回步骤1
        }
    }
    for !out.IsEmpty() {
        nodeArr = append(nodeArr, out.Pop().Val)
    }
    return nodeArr
}