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

题目描述

示例

代码

代码1 深度优先（dfs）遍历，把每个节点都进行一次深度优先遍历，找路径

/*
从根节点开始，对每个节点进行深度遍历
*/
function FindPath( root ,  sum ) {
    if(!root) return 0
    
    let count = 0 // 默认是0条路径
    
    // 对每个节点进行深度遍历，找路径
    dfs(root, sum)
    
    return count
    
    // 先遍历节点，然后对每个节点进行深度遍历 找符合结果的路径
    function dfs(root, sum){
        if(root === null) return;
        
        // 挨个节点遍历
        find(root, sum)
        dfs(root.left, sum)
        dfs(root.right, sum)
        
    }
    
    // 对每个节点进行遍历 找路径
    function find(root, sum){
        if(root === null) return // 都遍历到头了，还是没有符合题意的
        
        sum -= root.val
        
        if(sum === 0) {
            count++
        }
        
        find(root.left, sum) 
        find(root.right, sum)
    }
}

时间复杂度O(n^2)：假如是一条链表，需要找 n+(n-1)+(n-2)+...+2+1，总共(1+n)n/2，所以时间复杂度是O(n^2)

空间复杂度O(n)

题目来源

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