每日算法----145. 二叉树的后序遍历----2022/05/10
1. 题目描述
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
2. 示例
输入：root = [1,12,43,2,34,67] 输出：[2,34,12,67,43,1]
3. 思路
后序遍历：左右根
4. 遇上的问题
空间复杂度过高
5. 具体实现代码
自己写的代码
func postorderTraversal(root *TreeNode) []int {
if root == nil{
return nil
}
var valNodes []int
valNodes = append(valNodes, postorderTraversal(root.Left)...)
valNodes = append(valNodes, postorderTraversal(root.Right)...)
valNodes = append(valNodes, root.Val)
return valNodes
}
6. 官方题解
func reverse(a []int) {
for i, n := 0, len(a); i < n/2; i++ {
a[i], a[n-1-i] = a[n-1-i], a[i]
}
}
func postorderTraversal(root *TreeNode) (res []int) {
addPath := func(node *TreeNode) {
resSize := len(res)
for ; node != nil; node = node.Right {
res = append(res, node.Val)
}
reverse(res[resSize:])
}
p1 := root
for p1 != nil {
if p2 := p1.Left; p2 != nil {
for p2.Right != nil && p2.Right != p1 {
p2 = p2.Right
}
if p2.Right == nil {
p2.Right = p1
p1 = p1.Left
continue
}
p2.Right = nil
addPath(p1.Left)
}
p1 = p1.Right
}
addPath(root)
return
}
7 题目来源
有点急，只能先写一道了，又留坑。。------swrici
