后序遍历

树

说明

按左、右、根访问；适合先处理子树再汇总。

分析

先处理左右子树，最后处理当前节点，因此父节点能使用子节点已经计算好的结果。计算目录大小、释放树和树形动态规划都常采用后序。

以根2、左1、右3为例，访问顺序为1,3,2。处理根时左右结果已就绪，适合汇总高度和子树大小。每个节点访问一次；递归栈随树高变化，层序队列峰值则受层宽影响。

查看图表代码

适用前提与边界

每个节点只访问一次，时间 O(n)，递归栈与树高度相关。 输入必须是无环二叉树；空树不输出元素，递归栈取决于树高，不能一律估算成O(log n)。

示例输入与调用

root := &Node{Value: 2, Left: &Node{Value: 1}, Right: &Node{Value: 3}}
	var out []int
	Postorder(root, &out)
	fmt.Println(out)

运行输出

[1 3 2]

完整 Go 示例

package main

import "fmt"

type Node struct {
	Value       int
	Left, Right *Node
}

func Postorder(n *Node, out *[]int) {
	if n == nil {
		return
	}
	Postorder(n.Left, out)
	Postorder(n.Right, out)
	*out = append(*out, n.Value)
}

func main() {
	root := &Node{Value: 2, Left: &Node{Value: 1}, Right: &Node{Value: 3}}
	var out []int
	Postorder(root, &out)
	fmt.Println(out)
}