NC8 二叉树根节点到叶子节点和为指定值的路径

解法

function pathSum( root ,  sum ) {
    let res = []
    let path = []
    
    function DFS(root, acc){
        path.push(root.val)
        acc += root.val
        
        if(acc === sum && !root.left && !root.right){
            res.push([...path])
        }
        
        if(root.left){
            DFS(root.left, acc)
        }
        if(root.right){
            DFS(root.right, acc)
        }
        
        path.pop()
    }
    if(!root){
        return res
    }
    
    DFS(root, 0)
    return res
}

解析

经典的回溯算法

if(acc === sum && !root.left && !root.right){
    res.push([...path])
}

必须保证没有子节点才能确定答案

if(root.left){
    DFS(root.left, acc)
}
if(root.right){
    DFS(root.right, acc)
}

函数调用前就确定node != null，这样可以简化操作，如果在下一层判断有可能出错

path.push(root.val)
// DFS
path.pop()

回溯的核心部分, 成对的push pop保证调用结束数据及时弹出，防止对其他路径产生干扰