二叉树的所有路径

[louzhedong]

习题

出处 LeetCode 算法第257题

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

思路

采用DFS深度遍历的方式，遍历所有的结果

解答

/**
 * 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) {
  var res = [];
  if (!root) {
    return res;
  }

  var temp = [];
  DFS(root, temp, res);

  var newRes = [];
  res.map(function (item) {
    newRes.push(item.join('->'));
  });

  return newRes;
};

function DFS(root, temp, res) {
  temp.push(root.val);
  if (!root.left && !root.right) {
    res.push(copy(temp));
  }
  if (root.left) {
    DFS(root.left, copy(temp), res);
  }
  if (root.right) {
    DFS(root.right, copy(temp), res);
  }
}

function copy(array) {
  var newArray = [];
  for (var i = 0, len = array.length; i < len; i++) {
    newArray.push(array[i]);
  }
  return newArray;
}