美文网首页
2019-05-23bfs经典路径和

2019-05-23bfs经典路径和

作者: 咣超 | 来源:发表于2019-05-23 14:53 被阅读0次
    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);
        }
    }
    

    相关文章

      网友评论

          本文标题:2019-05-23bfs经典路径和

          本文链接:https://www.haomeiwen.com/subject/znavzqtx.html