No-recursion, easy to understand JAVA code with explanation, uses enhanced level-order traversal


  • 0
    M

    My code is simple logic. Use queues to visit all nodes in level order fashion, while keeping a parallel queue to record a list of sums in ancestors so far from root.

        public int pathSum(TreeNode root, int sum) {
            if(root==null) return 0;
            
            // queue needed for level-order traversal of all nodes
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            
            // this queeue: qli contains list of sums from root or any ancestor node for current node in queue q
            Queue<List<Integer>> qli = new LinkedList<>();
            List<Integer> li = new ArrayList<>();
            qli.add(li);
            
            
            int count=0;
            while(q.size()>0){
                li = qli.remove();
                root = q.remove();
                if(root.val==sum) count++;  // current node itself matches
                for(int val: li) 
                    if(  (val + root.val) == sum) count++;  // any sum from above plus current node matches
                    
                if(root.left!=null){
                    q.add(root.left);
                    List<Integer> lchild = new ArrayList<>();
                    for(int val: li)
                        lchild.add(root.val + val);  // enhance sums from root to this node, propagate towards descendents 
                    lchild.add(root.val); // also put current node as starting a new path
                    qli.add(lchild);
                }
                if(root.right!=null){
                    q.add(root.right);
                    // logic below same as lefft child 
                    List<Integer> lchild = new ArrayList<>(); 
                    for(int val: li)
                        lchild.add(root.val + val);
                    lchild.add(root.val);
                    qli.add(lchild);
                }
            }
            return count;
            
        }
    

Log in to reply
 

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