目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
二叉树后序遍历
访问量:1819
一、递归法
/** * 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 }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助