LeetCode112. 路径总和

☆☆☆方法1：递归

☆☆☆方法2：BFS。使用两个队列，分别存储将要遍历的节点，以及根节点到这些节点的路径和。

拓展练习：打印路径 ------->LeetCode113. 路径总和 II、 剑指24.二叉树中和为某一值的路径

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        /**
         * 方法1：递归
         */
        if (root == null) return false;
        // 到达叶子节点时，递归终止，判断 sum 是否符合条件。
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) ||
                hasPathSum(root.right, sum - root.val);
        /**
         * 方法2：BFS
         */
        /*
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> queue1 = new LinkedList<>();
        queue.offer(root);
        queue1.offer(root.val);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                int temp = queue1.poll();
                if (cur.left == null && cur.right == null) {
                    if (temp == sum) return true;
                }
                if (cur.left != null) {
                    queue.offer(cur.left);
                    queue1.offer(temp + cur.left.val);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                    queue1.offer(temp + cur.right.val);
                }
            }
        }
        return false;
        */
    }
}