3.binary-tree-paths.md

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

Note:

A leaf is a node with no children.

Example:

Input:

   1
 /   \
2     3
 \
  5

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

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

JavaScript

/**
 * 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 === null) {
        return [];
    }

    var result = [];
    result[0] = [root.val];

    runNext(root, result, 0);

    return transformation(result);
};

var search = function (node, stackMarix, oldStackIndex, isNew) {
    if (node === null) {
        return;
    }

    let stackIndex = oldStackIndex;
    if (isNew) {
        stackMarix[stackMarix.length] = stackMarix[stackIndex].slice();
        stackIndex = stackMarix.length - 1;
    }

    stackMarix[stackIndex].push(node.val);
    runNext(node, stackMarix, stackIndex);
};

var runNext = function (node, stackMarix, stackIndex) {
    if (node.left !== null && node.right !== null) {
        search(node.right, stackMarix, stackIndex, true);
        search(node.left, stackMarix, stackIndex, false);
    } else if (node.left === null) {
        search(node.right, stackMarix, stackIndex, false);
    } else {
        search(node.left, stackMarix, stackIndex, false);
    }
};


var transformation = function (matrix) {
    var result = [];
    for (var i = 0; i < matrix.length; ++i) {
        result.push(matrix[i].join('->'));
    }

    return result;
};