Facebook脸家 - Lexicographical path

Lexicographical path

        5
       / \
      3   2
     / \   \
    2   4   4
             \
              1

FB 面经，自底向上的 path 有【1,4,2,5】，【4,3,5】，【2,3,5】，要求按自底向上的 lexicographical order 返回排序的 path，比如在这里是 【1,4,2,5】, 【2,3,5】,【4,3,5】

Analysis: Post order, for each node keep left & right paths, merge 2 into one single path.
Complexity: O(nlgn), each node has at most lgn node in the path.

var binaryTreePaths = function(root) {
 var res = [];
 console.log(dfs(root, res));
 
 return res
};
function dfs(root, path){
    if(root === null){
 return [];
  }
  if(root.left === null && root.right === null){
      return [[root.val]];
  }
  var left = dfs(root.left, path);
  var right = dfs(root.right, path);
  var path = [];
  for(var key in left){
     left[key].push(root.val);
  }
  for(var key in right){
     right[key].push(root.val);
  }
  path = left.concat(right);
  return path;
}