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);
    }
}