437.路径总和III

437.路径总和III

5 years ago

source link: https://studygolang.com/articles/25995
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

题目描述

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

思路

既然题目中说明不超过1000个结点，可以使用一个长度为1000的数组，用于保存所有结点的值。
2.可以抽象理解为vals[0]是vals[1]的父节点，vals[1]是vals[2]的父节点。
一个结点的路径总和为：rootNum = rootNum + leftNum + rightNum。
4.可以使用递归来处理求和，递归到某一结点时，自底向上的相加结点求和与target即可。

Java代码实现

class Solution {
    private int num = 0;
    public int pathSum(TreeNode root, int sum) {
        int[] vals = new int[1000];
        
        return pathSumDS(root,0,vals,sum);
    }

    private int pathSumDS(TreeNode root,int depth,int[] vals,int sum){
        if(root == null)
            return 0;
        int rootVal = root.val;
        
        int num = 0;
        if(rootVal == sum){
            num = 1;
        }
        
        for(int i=depth-1;i>=0;i--){
            rootVal = rootVal + vals[i];
            if(rootVal == sum){
                num++;
            }
        }
        vals[depth] = root.val;
        
        int left = pathSumDS(root.left,depth+1,vals,sum);
        int right = pathSumDS(root.right,depth+1,vals,sum);
        
        return num+left+right;
    }
}

Golang代码实现

func pathSum(root *TreeNode, sum int) int {
    vals := make([]int,1000)
    return pathSumDS(root,sum,0,vals)
}

func pathSumDS(root *TreeNode, sum int, depth int,vals []int) int {
    if root == nil{
        return 0
    }
    
    rootVal := root.Val
    num := 0
    
    if rootVal == sum{
        num++
    }
    
    for i:=depth-1;i>=0;i--{
        rootVal += vals[i]
        if rootVal == sum{
            num++
        }
    }
    
    vals[depth] = root.Val
    
    left := pathSumDS(root.Left,sum,depth+1,vals)
    right := pathSumDS(root.Right,sum,depth+1,vals)
    
    return num+left+right
}

Recommend