姊妹篇:

leetcode-94 二叉树的中序遍历

leetcode-144 二叉树的前序遍历


后序遍历(LRD)是二叉树遍历的一种,也叫做后根遍历、后序周游,可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中,先左后右再根,即首先遍历左子树,然后遍历右子树,最后访问根结点。遍历路径为

为何”Postorder Traversal”缩写为LRD?


LRD其实是指遍历的顺序:

  • L为left
  • R为right
  • D为根节点,因为root与right首字母相同,为免歧义,用D代指根节点(Data),有的地方也用N来代指(Node)



相应的,前序遍历(Preorder Traversal ,DLR)和中序遍历(Inorder Traversal ,LDR)如下:

前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。遍历路径为

中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游,科记做左右根。在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。遍历路径为


所谓的”前/中/后”,是指访问到根节点的次序




145. 二叉树的后序遍历

难度: 困难




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) []int {
var res []int = make([]int,0)

if root == nil {
return res
}

//递归一定要写好终止条件
temp := postorderTraversal(root.Left)
res = append(res,temp...)

temp = postorderTraversal(root.Right)
res = append(res,temp...)

res = append(res,root.Val)

return res
}

时间复杂度/空间复杂度均为O(n)