import java.util.*;
public class Code_6路径总和 {
// 求一个二叉树的一条路径的和是否为给定的sum但是必须从根节点出发到叶子节点的和必须要到叶子节点
// 我们这里用的是bfs思路是先将root节点减掉sum加入队列中然后每扫到一个点就将值再减掉点的值直到结果为0
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int x) {
this.val = x;
}
}
public static boolean hasPathSum(TreeNode root, int sum) {
if(root == null) { // 如果根节点直接为 null 直接return false
return false;
}
if(root.val == sum && root.right == null && root.left == null) {
return true; // 如果根节点的值为sum同时他没有左右孩子return true
}
Queue<TreeNode> q = new LinkedList<TreeNode>();
root.val = sum - root.val;
q.offer(root);
while(!q.isEmpty()) {
for(int i = 0; i < q.size(); i++) {
TreeNode tmp = q.peek();
if(tmp.left != null) { // 是否存在左孩子
tmp.left.val = tmp.val - tmp.left.val; // 减掉它父亲节点的值
if(tmp.left.val == 0 && tmp.left.right == null && tmp.left.left == null) {
return true;
}
q.offer(tmp.left);
}
if(tmp.right != null) { // 右孩子
tmp.right.val = tmp.val - tmp.right.val;
if(tmp.right.val == 0 && tmp.right.right == null && tmp.right.left == null) {
return true;
}
q.offer(tmp.right);
}
q.poll(); // 这个点的所有节点已经搜完了因为是二叉树就两次搜索所以要弹出
}
}
return false;
}
public static void main(String[] args) {
TreeNode t1 = new TreeNode(1);
TreeNode t2 = new TreeNode(2);
TreeNode t3 = new TreeNode(5);
TreeNode t4 = new TreeNode(4);
t1.left = t2;
t1.right = t3;
t2.left = t4;
t2.right = null;
t3.left = null;
t3.right = null;
t4.left = null;
t4.right = null;
boolean f = hasPathSum(t1, 1);
System.out.println(f);
}
}
网友评论