牛客NC162 二叉树中和为某一值的路径(三)【中等 dfs C++、Java、Go、PHP】

题目

题目链接：
https://www.nowcoder.com/practice/965fef32cae14a17a8e86c76ffe3131f

思路

既然要找所有路径上节点和等于目标值的路径个数，那我们肯定先找这样的路径起点啊，
但是我们不知道起点究竟在哪里，
而且任意节点都有可能是起点，那我们就前序遍历二叉树的所有节点，每个节点都可以作
为一次起点，即子树的根节点。
具体做法：
     step 1：每次将原树中遇到的节点作为子树的根节点送入dfs函数中查找有无路径，
     如果该节点为空则返回。
     step 2：然后递归遍历这棵树每个节点，每个节点都需要这样操作。
     step 3：在dfs函数中，也是往下递归，遇到一个节点就将sum减去节点值再往下。
     step 4：剩余的sum等于当前节点值则找到一种情况。
1
2
3
4
5
6
7
8
9
10

参考答案C++

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return int整型
     */
    int FindPath(TreeNode* root, int sum) {
    
            /*
            既然要找所有路径上节点和等于目标值的路径个数，那我们肯定先找这样的路径起点啊，但是我们不知道起点究竟在哪里，
            而且任意节点都有可能是起点，那我们就前序遍历二叉树的所有节点，每个节点都可以作为一次起点，即子树的根节点。
            具体做法：
               step 1：每次将原树中遇到的节点作为子树的根节点送入dfs函数中查找有无路径，如果该节点为空则返回。
               step 2：然后递归遍历这棵树每个节点，每个节点都需要这样操作。
               step 3：在dfs函数中，也是往下递归，遇到一个节点就将sum减去节点值再往下。
               step 4：剩余的sum等于当前节点值则找到一种情况。
            */

            int cnt = 0;
            int* ptr = &cnt;
            f(root, sum, ptr);
            return cnt;
        }

        void f(TreeNode * root, int sum, int* cnt) {
            if (root == nullptr) {
                return;
            }

            //以root根节点的路径数
            dfs(root, sum, cnt);
            //以root子节点为根的路径
            f(root->left, sum, cnt);
            f(root->right, sum, cnt);
        }

        void dfs(TreeNode * root, int sum, int* cnt) {
            if (root == nullptr) return;
            //符合要求，ans++
            if (root->val == sum) {
               // cout << "ddd" << endl;
                (*cnt)++;  //必须这样写，不能这样写*cnt++
            }

            //继续查找子节点
            dfs(root->left, sum - root->val, cnt);
            dfs(root->right, sum - root->val, cnt);
        }
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

参考答案Java

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return int整型
     */
    public int FindPath (TreeNode root, int sum) {

        /*
        既然要找所有路径上节点和等于目标值的路径个数，那我们肯定先找这样的路径起点啊，但是我们不知道起点究竟在哪里，
        而且任意节点都有可能是起点，那我们就前序遍历二叉树的所有节点，每个节点都可以作为一次起点，即子树的根节点。
        具体做法：
            step 1：每次将原树中遇到的节点作为子树的根节点送入dfs函数中查找有无路径，如果该节点为空则返回。
            step 2：然后递归遍历这棵树每个节点，每个节点都需要这样操作。
            step 3：在dfs函数中，也是往下递归，遇到一个节点就将sum减去节点值再往下。
            step 4：剩余的sum等于当前节点值则找到一种情况。
         */

        int[] ans = {0};
        f(root, sum, ans);
        return ans[0];
    }

    public void f(TreeNode root, int sum, int[] ans) {
        //查询以某节点为根的路径数
        if (root == null) return ;
        dfs(root, sum, ans);

        //以其子节点为新的根节点的路径数
        f(root.left, sum, ans);
        f(root.right, sum, ans);
    }


    public void dfs(TreeNode root, int sum, int[] ans) {
        if (root == null) return;
        //符合目标,ans[0]++
        if (sum == root.val) ans[0]++;
        //子节点继续查找
        dfs(root.left, sum - root.val, ans);
        dfs(root.right, sum - root.val, ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

参考答案Go

package main

import . "nc_tools"

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @param sum int整型
 * @return int整型
 */
func FindPath(root *TreeNode, sum int) int {
	/*
	   既然要找所有路径上节点和等于目标值的路径个数，那我们肯定先找这样的路径起点啊，但是我们不知道起点究竟在哪里，
	   而且任意节点都有可能是起点，那我们就前序遍历二叉树的所有节点，每个节点都可以作为一次起点，即子树的根节点。
	   具体做法：
	       step 1：每次将原树中遇到的节点作为子树的根节点送入dfs函数中查找有无路径，如果该节点为空则返回。
	       step 2：然后递归遍历这棵树每个节点，每个节点都需要这样操作。
	       step 3：在dfs函数中，也是往下递归，遇到一个节点就将sum减去节点值再往下。
	       step 4：剩余的sum等于当前节点值则找到一种情况。
	*/

	ans := [1]int{0}
	f(root, sum, &ans)
	return ans[0]
}

func f(root *TreeNode, sum int, ans *[1]int) {
	if root == nil {
		return
	}
	//查询以root为根的路径数
	dfs(root, sum, ans)
	//查询以root子节点为根的路径数
	f(root.Left, sum, ans)
	f(root.Right, sum, ans)
}

func dfs(root *TreeNode, sum int, ans *[1]int) {
	if root == nil {
		return
	}
	//符合目标，ans[0]++
	if root.Val == sum {
		ans[0]++
	}

	//子节点继续查找
	dfs(root.Left, sum-root.Val, ans)
	dfs(root.Right, sum-root.Val, ans)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

参考答案PHP

<?php

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param sum int整型 
 * @return int整型
 */
function FindPath( $root ,  $sum )
{
       /*
           既然要找所有路径上节点和等于目标值的路径个数，那我们肯定先找这样的路径起点啊，但是我们不知道起点究竟在哪里，
           而且任意节点都有可能是起点，那我们就前序遍历二叉树的所有节点，每个节点都可以作为一次起点，即子树的根节点。
           具体做法：
               step 1：每次将原树中遇到的节点作为子树的根节点送入dfs函数中查找有无路径，如果该节点为空则返回。
               step 2：然后递归遍历这棵树每个节点，每个节点都需要这样操作。
               step 3：在dfs函数中，也是往下递归，遇到一个节点就将sum减去节点值再往下。
               step 4：剩余的sum等于当前节点值则找到一种情况。
        */
    $ans=[0];
    f($root,$sum,$ans);
    return $ans[0];
}

function f($root,$sum,&$ans){
    if($root ==null) return;

    //以root为根的节点dfs
    dfs($root,$sum,$ans);
    //以root的子节点为根dfs
    f($root->left,$sum,$ans);
    f($root->right,$sum,$ans);
}

function dfs($root,$sum,&$ans){
    if($root ==null) return;
    //符合要求，ans++
    if($root->val ==$sum){
        $ans[0]++;
    }

    //子节点继续查找
    dfs($root->left,$sum-$root->val,$ans);
    dfs($root->right,$sum-$root->val,$ans);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57