题目

点击前往

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

1
2
输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：

1
2
输入：root = []
输出：[]

解题思路

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    let result = [];
    const dfs = function(root){
        if(root == null) return;
        dfs(root.left);
        dfs(root.right);
        result.push(root.val);
    }
    dfs(root);
    return result;
};

迭代

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
28
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    let result = [];
    if(!root) return result;
    // 根节点先入栈
    let stack = [root];
    let cur = null
    while(stack.length){
        // 栈顶出战
        cur = stack.pop();
        result.push(cur.val);
        // 中右左进栈
        cur.left && stack.push(cur.left);
        cur.right && stack.push(cur.right);
    }
    return result.reverse();
};