145. Binary Tree Postorder Traversal

Leetcode

https://leetcode.com/problems/binary-tree-postorder-traversal/

題目

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

解答

• 方法一

Recursion

var postorderTraversal = function(root) {
    if(root === null) return [];
    
    const result = [];
    const postorder = (node) => {
        if (node.left) postorder(node.left);
        if (node.right) postorder(node.right);
        result.push(node.val);
    };
    postorder(root);
    return result;
};

Runtime: 92 ms, faster than 45.15% of JavaScript online submissions for Binary Tree Postorder Traversal.

Memory Usage: 42.3 MB, less than 30.59% of JavaScript online submissions for Binary Tree Postorder Traversal.

• 方法二

Iteration

var postorderTraversal = function(root) {
    if(root === null) return [];
    
    const result = [];
    const stack = [root];
    while(stack.length) {
        const node = stack.pop();
        result.push(node.val);
        // 左邊先放入 stack 的，最後會是排序在前面的
        // postorder left -> right -> root
        // 這裡的 stack 反向放 root -> right -> left
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
    
    // 倒轉過來
    return result.reverse();
};

Runtime: 106 ms, faster than 25.24% of JavaScript online submissions for Binary Tree Postorder Traversal.

Memory Usage: 42.1 MB, less than 38.09% of JavaScript online submissions for Binary Tree Postorder Traversal.

參考資料

https://jstechroad.com/algorithms/leetcode-145-binary-tree-postorder-traversal-javascript/