leetcode-145 二叉树的后序遍历

Tree
留言

姊妹篇:

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
27
/**
 * 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)