题解 | #牛的奶量统计II#
牛的奶量统计II
https://www.nowcoder.com/practice/9c56daaded6b4ba3a9f93ce885dab764
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 targetSum int整型
* @return bool布尔型
*/
public boolean hasPathSumII (TreeNode root, int targetSum) {
// write code here
if (root == null) return false;
return hasPathSum(root, targetSum) ||
hasPathSumII(root.left, targetSum) ||
hasPathSumII(root.right, targetSum);
}
public boolean hasPathSum (TreeNode root, int sum) {
// write code here
if (root == null) {
return false;
}
return root.val == sum ||
hasPathSum(root.left, sum - root.val) ||
hasPathSum(root.right, sum - root.val);
}
}
本题知识点分析：
1.深度优先搜索
2.二叉搜索数
本题解题思路分析：
1.编写DFS深度优先搜索函数计算路径和
2.如果节点为null,返回false
3.如果节点左孩子和右孩子都为null,并且当前节点+sum==目标和，返回true
4.递归左子树和右子树并传递相对应的现有的sum
5.在主函数中递归左子树和右子树
查看4道真题和解析
投递美团等公司8个岗位 >