437.路径总和III

youzhihua · · 520 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

题目描述

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

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

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

二叉树不超过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

思路

  1. 既然题目中说明不超过1000个结点,可以使用一个长度为1000的数组,用于保存所有结点的值。
    2.可以抽象理解为vals[0]是vals[1]的父节点,vals[1]是vals[2]的父节点。
  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
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:youzhihua

查看原文:437.路径总和III

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

520 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传