讨论/《零起步学算法》 - 练习:路径总和/
《零起步学算法》 - 练习:路径总和
共 1 个回复

两个队列,一个队列存节点,另一个队列存值

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
      //广度优先搜索 => 层序遍历 => bfs
      //队列
      if(root == null) {
        return false;
      }
      Deque<TreeNode> queue1 = new LinkedList<>();
      Deque<Integer> queue2 = new LinkedList<>();
      queue1.offerLast(root);
      queue2.offerLast(root.val);
      while(!queue1.isEmpty()) {
        TreeNode head1 = queue1.pollLast();
        int head2 = queue2.pollLast();
        TreeNode leftNode = head1.left;
        TreeNode rightNode = head1.right;
        if(leftNode == null && rightNode == null) {
          if(head2 == targetSum) {
            return true;
          }
          continue;
        }
        if(leftNode != null) {
          queue2.offerLast(leftNode.val + head2);
          queue1.offerLast(leftNode);
        }
        if(rightNode != null) {
          queue2.offerLast(rightNode.val + head2);
          queue1.offerLast(rightNode);
        }
      }
      return false;
    }
}
1