Leetcode（一、二叉树路径求和题）

100 阅读 0 评论 66 点赞

我是靠谱客的博主优雅路灯，最近开发中收集的这篇文章主要介绍Leetcode（一、二叉树路径求和题），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

做这个题之前首先是要明白递归的用法，如果不知道的可以去看看https://www.cnblogs.com/zuixime0515/p/10513254.html
题目：
在这里插入图片描述

将题目转换成对象的形式，如下所示：
var tree = {
val: 5,
left: {
val: 4,
left: {
val: 11,
left: {
val: 7,
left: null,
right: null
},
right: {
val: 2,
left: null,
right: null
}
},
right: null
},
right: {
val: 8,
left: {
val: 13,
left: null,
right: null
},
right: {
val: 4,
left: null,
right: {
val: 1,
left: null,
right: null
}
}
}
}

先介绍下总体的思路，就是通过一层层的递归调用，去记录遍历每个节点，直到遍历到底层的叶子节点之后，就停止遍历。再将所有的路径节点加到一起。
我将在下面代码中做详细的注释，希望对大家能提供一个思路。

        var hasPathSum = function(root, sum) {
        
            var paths = [];   满足条件的最终结果数组

            function onepath(node, path) {  递归函数 其中node是树节点 path是paths中的具体情况
                if (!node) return;
                path.push(node.val); 将上一个节点的值推到path数组中
                if (node.left == null && node.right == null) {  大家都是知道的常识是什么是叶子节点呢？？？叶子节点说白了就是它的下面再也没有分支啦，所以直到它左右两面都没有叶子分支的时候就可以，跳出去了。
              
                    console.log(path);
                    这个判断是用来计算路径中所有数值是否满足和的
                    if (path.reduce((a, b) => {
                            a + b
                        }) == sum) {

满足条件的就推到最终的数组里面去
                        paths.push(path);
                    };
                    return;
                    当然不能排除只有一个节点的时候，这时候就得传入对应的节点值
                } else if (node.left == null && node.right != null) {

                    onepath(node.right, path.slice(0));
                                    当然不能排除只有一个节点的时候，这时候就得传入对应的节点值
                } else if (node.left != null && node.right == null) {
                    onepath(node.left, path.slice(0));
                } else {
                如果都不是空，需要将左右两个节点都传进去
                    onepath(node.right, path.slice(0));
                    onepath(node.left, path.slice(0));
                }




            }
            onepath(root, []);
        };

        hasPathSum(tree, 22);