[Accepted] Elegant BFS Solution


  • 0
    T

    The idea is to create a wrapper class with one Integer field to signify what the current node's val should be.

    public class Solution {
        static class Result {
            TreeNode node;
            int toMatch;
            
            public Result(TreeNode node, int toMatch) {
                this.node = node;
                this.toMatch = toMatch;
            }
        }
        public boolean hasPathSum(TreeNode root, int sum) {
            if (root == null) { return false;}
            Queue<Result> q = new LinkedList<Result>();
            q.offer(new Result(root, sum));
            while(!q.isEmpty()) {
                Result temp = q.poll();
                if (temp.node.val == temp.toMatch && temp.node.left == null && temp.node.right == null) { return true;}
                if (temp.node.left != null) {
                    q.offer(new Result(temp.node.left, temp.toMatch - temp.node.val));
                }
                if (temp.node.right != null) {
                    q.offer(new Result(temp.node.right, temp.toMatch - temp.node.val));
                }
            }
            return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.