前言
持续更新了
正文
问题来源
本问题来自leetcode上的145题。
问题描述
给定一个二叉树，返回它的 后序 遍历。
示例 1:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
分析：
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。
第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
/**
* 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
}
var pre *TreeNode
var cur *TreeNode
stack := make([]*TreeNode, 0)
stack = append(stack, root)
res := make([]int, 0)
for len(stack) > 0 {
cur = stack[len(stack)-1]
if (cur.Left == nil && cur.Right == nil) || (pre != nil && (pre == cur.Left||pre == cur.Right)) { // 这个判断非常关键
res = append(res, cur.Val)
stack = stack[:len(stack)-1] // 左右子树都处理完成才弹出
pre = cur
continue // 相当于else后面左右的判断
}
if cur.Right != nil { // 先压右
stack = append(stack, cur.Right)
}
if cur.Left != nil { // 再压左
stack = append(stack, cur.Left)
}
}
return res
}
总结：
勤思考。
结语
不管怎么样好好加油。
