package com.example.lettcode.dailyexercises;
/**
* @Class HasPathSum
* @Description 112. 路径总和
* 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,
* 这条路径上所有节点值相加等于目标和。
* <p>
* 说明: 叶子节点是指没有子节点的节点。
* 示例:
* 给定如下二叉树,以及目标和 sum = 22,
* <p>
* 5
* /
* 4 8
* / /
* 11 13 4
* /
* 7 2 1
* 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
* @Author
* @Date 2020/7/7
**/
public class HasPathSum {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
}
/**
* 递归方式
*/
public static boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
// 如果是叶子节点,判断节点的值与sum是否相等
if (root.left == null && root.right == null) return root.val == sum;
return hasPathSum(root.left, sum - root.val)
|| hasPathSum(root.right, sum - root.val);
}
// 测试用例
public static void main(String[] args) {
TreeNode root = new TreeNode(5);
TreeNode treeNode1 = new TreeNode(4);
TreeNode treeNode2 = new TreeNode(8);
root.left = treeNode1;
root.right = treeNode2;
TreeNode treeNode3 = new TreeNode(11);
treeNode1.left = treeNode3;
TreeNode treeNode4 = new TreeNode(13);
TreeNode treeNode5 = new TreeNode(4);
treeNode2.left = treeNode4;
treeNode2.right = treeNode5;
TreeNode treeNode6 = new TreeNode(7);
TreeNode treeNode7 = new TreeNode(2);
treeNode3.left = treeNode6;
treeNode3.right = treeNode7;
TreeNode treeNode8 = new TreeNode(1);
treeNode5.right = treeNode8;
int sum = 22;
boolean ans = hasPathSum(root, sum);
System.out.println("HasPathSum demo01 result:" + ans);
}