每日算法----145. 二叉树的后序遍历----2022/05/10

每日算法----145. 二叉树的后序遍历----2022/05/10 2022-05-12 265

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
}