Java, recursion solution with explaination


  • 0
    M

    The idea is the same as the problem of finding a path from root to leaf ("pathSum_m" method). The difference is we can have a path not starting from root which add to the "sum". So we can add two more recursions from left and right child of the root. Below is the code. Honestly it took me a while to figure it out. Hope it's helpful.

    public class Solution {
        public int pathSum(TreeNode root, int sum) {
            if(root==null)
                return 0;
            else{
                Total total= new Total();
                int orig_sum=sum;
                Set<TreeNode> visited = new HashSet<TreeNode>();
                pathSum_m(root, sum, total);
                return total.all+pathSum(root.left,sum)+pathSum(root.right,sum);
                
                
            }
        }
        
        public void pathSum_m(TreeNode root, int sum, Total total) {
            
            if(root==null)
                return;
            else{
                int subsum = sum-root.val;
                //sum=orig_sum;
                if(subsum==0){
                    total.all++;
                }
                
                if(root.left!=null){
                    pathSum_m(root.left, subsum, total);
                }
                
                
                
                if(root.right!=null){
                    pathSum_m(root.right, subsum, total);
    
                }
    
            }
        
            }
        
        
        public static class Total{
            private int all=0;
        }
    }
    

Log in to reply
 

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