二叉树中和为某一值的路径(二)

题目描述

示例

代码

代码1 深度优先遍历（DFS）遍历的过程中把路径记录下来

/*
深度优先遍历 
log(root.val)
dfs(root.left)
dfs(root.right)
1. 遍历，每遍历一个节点，sum就减去val
2. 当遍历到叶子节点时，sum正好等于零表示，这条路径正确
3. 使用一个数组存储临时的路径记录
4. 每次发生回溯时，将临时数组的最后一个值pop出去
*/
function FindPath(root, expectNumber)
{
    if(!root) return []
    
    let result = [] // 最终返回的结果
    let path = [] // 记录遍历的路径
    // 开始dfs遍历
    dfs(root, expectNumber)
    return result
    
    // 递归遍历
    function dfs(root, expectNumber){
        // 出口
        if(!root) return; // 到头了
        
        path.push(root.val) // 记录遍历路径
        
        // 在当前路径，每遍历一个节点就减去一个值，
        // 当正好等于0时，说明这条路径就是一个结果
        expectNumber -= root.val 
        
        // 如果遍历到了叶子节点，且expectNumber正好为0
        if(!root.left && !root.right && expectNumber===0) {
            // 说明这是个结果，把结果保存起来
            result.push([...path])
        }
        
        // 递归往下找
        dfs(root.left, expectNumber)
        dfs(root.right, expectNumber)
        
        // 发生回溯的过程中，把路径的最后一个值pop出去
        path.pop()
    }
}

时间复杂度O(N)：递归遍历的节点个数为N

空间复杂度O(N)

题目来源

JZ34 二叉树中和为某一值的路径(二)