讨论/求职面试/剑指Offer第34题:求和为某值的路径 有问题求助/
剑指Offer第34题:求和为某值的路径 有问题求助

问题描述

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

求助各位大佬:在程序中,我用pathArray储存和为22的路径,然后将其添加进resultArray中,并最终返回resultArray,但是结果总是两个空列表: [[],[]](应该是[[5,4,11,2],[5,8,4,5]]才对)。当我把程序稍微一改,遍历pathArray,并将其元素存储于一个局部定义的列表f中,再将f,push到resultArray中,输出就正常了,请问这是什么原因呢

改之前程序:
var pathSum = function(root, sum) {
    let pathnum = 0;
    let pathArray = [];
    let result = 0;
    let resultArray = [];
    function dfs(root,sum){
        if(root != null){
            pathnum += root.val;
            pathArray.push(root.val);
            if(pathnum === sum &&root.left == null&&root.right==null){
                result++;
                 resultArray.push(pathArray); 
            }
            dfs(root.left,sum);
            dfs(root.right,sum);
            pathnum -= root.val;
            pathArray.pop();
        }
    }
    dfs(root,sum);
    return resultArray;
    // 最后的结果是 [[],[]]
改之后的程序,输出正常:
var pathSum = function(root, sum) {
    let pathnum = 0;
    let pathArray = [];
    let result = 0;
    let resultArray = [];
    function dfs(root,sum){
        if(root != null){
            pathnum += root.val;
            pathArray.push(root.val);
            if(pathnum === sum &&root.left == null&&root.right==null){
                result++;
               // resultArray.push(pathArray); 
                const f = [];   //在这里进行修改的
                for(let i = 0;i<pathArray.length;i++){  
                    f.push(pathArray[i]);
                }
                resultArray.push(f);
       
            }
            dfs(root.left,sum);
            dfs(root.right,sum);
            pathnum -= root.val;
            pathArray.pop();
        }
    }
    dfs(root,sum);
    return resultArray;
};
//正常输出[[5,4,11,2],[5,8,4,5]]
9
共 2 个回复

非常感谢大佬!解答了我的疑惑

数组是引用类型,resultArray.push(pathArray),存入的是pathArray对象的引用,最终resultArray中所有的引用都指向了pathArray对象,而pathArray中的元素在回溯的过程中会被pop掉,最后输出就是一堆空数组。
第二种操作将pathArray元素复制到了一个新的数组中,所以就是正确的。