257. Binary Tree Paths

Leetcode

https://leetcode.com/problems/binary-tree-paths/

題目

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

Example 2:

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

解答

• 方法一

Iteration

var binaryTreePaths = function(root) {
    if(root === null) return [];

    const res = [];
    const queue = [{
        val: [],
        node: root
    }];
    while(queue.length) {
        const curr = queue.shift();
        const node = curr.node;
        const val = [...curr.val, node.val];
        if (!node.left && !node.right) res.push(val.join('->'));
        if (node.left) {
            queue.push({
                val,
                node: node.left
            })
        }
        if (node.right) {
            queue.push({
                val,
                node: node.right
            })
        }
    }
    return res;
};

Runtime: 90 ms, faster than 51.28% of JavaScript online submissions for Binary Tree Paths.

Memory Usage: 44.6 MB, less than 8.23% of JavaScript online submissions for Binary Tree Paths.

• 方法二

Recursion

var binaryTreePaths = function(root) {
    const res = [];
    const helper = (node, path) => {
        if (!node) return;
        path += node.val.toString();
        if (!node.left && !node.right) res.push(path);
        path += "->"
        helper(node.left, path);
        helper(node.right, path);
    }
    
    helper(root, '');
    return res;
};

Runtime: 142 ms, faster than 5.13% of JavaScript online submissions for Binary Tree Paths.

Memory Usage: 43.4 MB, less than 73.18% of JavaScript online submissions for Binary Tree Paths.