sl1673495 / leetcode-javascript

:beers: 喝杯小酒,一起做题。前端攻城狮从零入门算法的宝藏题库,根据知名算法老师的经验总结了 100+ 道 LeetCode 力扣的经典题型 JavaScript 题解和思路。已按题目类型分 label,一起加油。
2.08k stars 344 forks source link

路径总和 II-113 #27

Open sl1673495 opened 4 years ago

sl1673495 commented 4 years ago

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

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

示例:

给定如下二叉树,以及目标和 sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/path-sum-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

典型的可以用 DFS 来解决的问题,定义一个 search 方法并且参数里带一个用来收集路径的 paths 数组,每当到达叶子节点(没有 left 也没有 right),就计算一把路径的总和,如果等于目标值就 push 到结果数组里。(注意这里要浅拷贝一下,防止下面的计算污染这个数组)

任何一个节点处理完成时,都要把当前节点 pop 出 paths 数组。

let pathSum = function (root, sum) {
  let res = [];
  let search = function (node, paths) {
    if (isInvalid(node)) return;
    paths.push(node.val);
    if (node.left) {
      search(node.left, paths);
    }
    if (node.right) {
      search(node.right, paths);
    }
    if (!node.left && !node.right) {
      if (sumVals(paths) === sum) {
        res.push(paths.slice());
      }
    }
    paths.pop();
  };
  search(root, []);
  return res;
};

function sumVals(nodes) {
  return nodes.reduce((prev, val) => {
    prev += val;
    return prev;
  }, 0);
}

function isInvalid(node) {
  return !node || node.val === undefined || node.val === null;
}
chengpeixin commented 4 years ago

data.json

{
    "code": 1,
    "children": [
        {
            "code": 2,
            "children": [
                {
                    "code": 5,
                    "children": [
                        {
                            "code": 7
                        },
                        {
                            "code": 8
                        }
                    ]
                }
            ]
        },
        {
            "code": 3,
            "children": [
                {
                    "code": 12,
                    "children": [
                        {
                            "code": 13
                        },
                        {
                            "code": 15
                        }
                    ]
                },
                {
                    "code": 90,
                    "children": [
                        {
                            "code": 99
                        },
                        {
                            "code": 91
                        },
                        {
                            "code": 78
                        },
                        {
                            "code": 66
                        },
                        {
                            "code": 16,
                            "children": [
                                {
                                    "code": 74,
                                    "children": [
                                        {
                                            "code": 73,
                                            "children": [
                                                {
                                                    "code": 70,
                                                    "children": [
                                                        {
                                                            "code": 61
                                                        },
                                                        {
                                                            "code": 62
                                                        },
                                                        {
                                                            "code": 63,
                                                            "children": [
                                                                {
                                                                    "code": 888
                                                                },
                                                                {
                                                                    "code": 999,
                                                                    "children": [
                                                                        {
                                                                            "code": 777
                                                                        },
                                                                        {
                                                                            "code": 222
                                                                        },
                                                                        {
                                                                            "code": 111
                                                                        }
                                                                    ]
                                                                },
                                                                {
                                                                    "code": 555
                                                                }
                                                            ]
                                                        }
                                                    ]
                                                }
                                            ]
                                        }
                                    ]
                                }
                            ]
                        }
                    ]
                }
            ]
        },
        {
            "code": 4,
            "children": [
                {
                    "code": 21,
                    "children": [
                        {
                            "code": 26
                        },
                        {
                            "code": 95
                        },
                        {
                            "code": 75
                        }
                    ]
                },
                {
                    "code": 36,
                    "children": [
                        {
                            "code": 38,
                            "children": [
                                {
                                    "code": 39
                                }
                            ]
                        }
                    ]
                }
            ]
        }
    ]
}

index.js

const data = require('./data.json')

function isChildren(node){
    return node.children?true:false
}
var pathCode = function(node, code,key) {
    const pathes = [];
    _pathCode(node, code, pathes, [],key);
    return pathes;
};

function _pathCode(node, code, pathes, path,key) {
    path = [...path, node[key]];
    if (node[key]===code){
        pathes.push(...path)
        return 
    }
    if (isChildren(node)){
        for (let i=0;i<node.children.length;i++){
            _pathCode(node.children[i],code,pathes,path,key)
        }
    }
}

const paths = pathCode(data,555,'code')
vortesnail commented 3 years ago

大佬的思路还是很明确的,一看就懂,但是 sumVals 这个函数对于节点较多时候还是比较耗时的,可以优化一下:

var pathSum = function (root, targetSum) {
  const res = [];
  helper(root, [], 0, targetSum, res);
  return res;
};

var helper = function (node, paths, sum, targetSum, res) {
  if (!node) return;
  paths.push(node.val);
  sum += node.val;

  if (node.left) helper(node.left, paths, sum, targetSum, res);
  if (node.right) helper(node.right, paths, sum, targetSum, res);

  if (!node.left && !node.right) {
    if (sum === targetSum) {
      res.push(paths.slice());
    }
  }

  // 退出当前递归,一定要将这次递归的节点去掉,因为要回到父节点重新开启另一条路径。
  paths.pop();
  sum -= node.val;
}