Binary Tree Paths#

Given a binary tree, return all the paths from the root node to the leaf nodes.

Explanation: A leaf node refers to a node with no child nodes.

Example#

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All the paths from the root node to the leaf nodes are: 1->2->5, 1->3

Solution#

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
    if(!root) return [];
    var target = [];
    var dfs = function(root, tmp){
        if(!root) return void 0;
        if(!root.left && !root.right){
            target.push(tmp);
            return void 0;
        }
        if(root.left) dfs(root.left, `${tmp}->${root.left.val}`);
        if(root.right) dfs(root.right, `${tmp}->${root.right.val}`);
    }
    dfs(root, `${root.val}`)
    return target;
};

Approach#

Traverse the binary tree in a depth-first manner, concatenating the nodes of the paths into strings. After reaching the root node, push the concatenated string into the target array. If there are no nodes, return an empty array. Define the target array target. If there are no defined nodes, return empty. If there are no left and right children, i.e., it is a leaf node, push the cached string into the array and return to end the recursion. If a left child exists, recursively traverse to the left and concatenate the left child's node value to the string and pass it. If a right child exists, recursively traverse to the right and concatenate the right child's node value to the string and pass it. Then start the recursion. Note that the problem requires strings instead of numbers, so the node value at the start of the recursion needs to be converted to a string. Finally, return the target array.

Daily Problem#

https://github.com/WindrunnerMax/EveryDay

Reference#

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