牛客题霸——NC8 二叉树根节点到叶子节点和为指定值的路径(Javascript)

本文主要是介绍牛客题霸——NC8 二叉树根节点到叶子节点和为指定值的路径(Javascript)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、题目地址

https://www.nowcoder.com/practice/840dd2dc4fbd4b2199cd48f2dadf930a?tpId=188&&tqId=38567&rp=1&ru=/ta/job-code-high-week&qru=/ta/job-code-high-week/question-ranking

二、具体代码

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param root TreeNode类 
  * @param sum int整型 
  * @return int整型二维数组
  */
function pathSum( root ,  sum ) {
    //1、如果root是空树,直接返回
    if(!root) {
        return [];
    }
    //2、定义存放所有可行路径的最后结果数组res
    let res = [];
    //3、定义每一条可行路径的结果数组temp
    let temp = [];
    //4、定义递归函数dfs,求出最后结果res
    function dfs(root, sum) {
        temp.push(root.val);
        //4.1、当递归到没有子树且当前节点的值等于sum时
        if((root.val === sum) && (root.left === null) && (root.right === null)) {
            //4.2、将当前节点加入到temp数组
            /*
                注意:当一个数组如何加入到另一个数组，需要浅拷贝
             */
            res.push(temp.slice());
        }else {
            //4.3、左子树存在,递归左子树
            if(root.left) {
                dfs(root.left, sum - root.val);
            }
            //4.4、右子树存在,递归右子树
            if(root.right) {
                dfs(root.right, sum - root.val);
            }
        }
        //4.5、当当前路径的和等于sum时,需要一个一个弹出temp中的值,为下一条路径做准备
        temp.pop();
    }
    //5、调用递归函数dfs
    dfs(root, sum);
    return res;
}
module.exports = {
    pathSum : pathSum
};

这篇关于牛客题霸——NC8 二叉树根节点到叶子节点和为指定值的路径(Javascript)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！