二叉树后序遍历
访问量:451

一、递归法

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 左-右-根
func postorderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    
    rs := make([]int, 0)
    if root.Left != nil {
        rs = append(rs, postorderTraversal(root.Left)...)
    }
    
    if root.Right != nil {
        rs = append(rs, postorderTraversal(root.Right)...)
    }
    
    rs = append(rs, root.Val)
    
    return rs
}

二、非递归法

1、利用倒叙法

后续遍历输出规则为“左-右-根”,如果我们能够输出“跟-右-左”,然后翻转一波即可。思路如下:

首先将root节点插入栈中

1、若栈不为空,取出栈顶元素,访问该元素,记录当前值

2、若弹出的元素,左节点不为空,将左节点插入栈用

3、若弹出饿元素,右节点不为空,将右节点插入栈用

重复上面1~3步骤,直到栈为空,最后翻转一下记录的值即可,代码实现如下:

// 二叉树后序遍历非递归
// 左-右-根
func postorderTraversal(root *TreeNode) []int {
   if root == nil {
      return nil
   }

   if root.Left == nil && root.Right == nil {
      return []int{root.Val}
   }

   rs := make([]int, 0)
   s := new(Stack)

   // 插入根节点
   s.Push(root)

   for ! s.IsEmpty() {
      curNode := s.Pop()
      rs = append(rs, curNode.Val)

      // 先插入left,后插入right,这样能保证先取出right,后取left
      if curNode.Left != nil {
         s.Push(curNode.Left)
      }

      if curNode.Right != nil {
         s.Push(curNode.Right)
      }
   }

   // 翻转切片
   for i, j := 0, len(rs)-1; i < j; i, j = i+1, j-1 {
      rs[i], rs[j] = rs[j], rs[i]
   }

   return rs
}