Clean Java DFS solution (preorder traversal)


  • 20
    public class Solution {
        int total;
        
        public int sumNumbers(TreeNode root) {
            total = 0;
            helper(root, 0);
            return total;
        }
        
        void helper(TreeNode root, int sum) {
            if (root == null) return;
            
            sum = sum * 10 + root.val;
            
            if (root.left == null && root.right == null) {
                total += sum;
                return;
            }
            
            helper(root.left, sum);
            helper(root.right, sum);
        }
    }

  • 0
    T

    very neat code.


  • 0
    F
    This post is deleted!

  • 1
    H
    public int sumNumbers(TreeNode root) {
        return DFS(root, 0);
    }
    
    public int DFS(TreeNode root, int sum){
        if(root == null) return 0;
        int newSum = sum*10 + root.val;
        if(root.left == null && root.right == null) return newSum;
        return DFS(root.left, newSum) + DFS(root.right, newSum);
    }
    

    Your code can be further optimized by removing the class variable


  • 0
    R

    SIMPLE TO UNDERSTAND, JUST LIKE PREORDER RECURSION TRAVERSAL IS DONE

    public class Solution {
    
    ArrayList<Integer> nodes = new ArrayList<Integer>(); // contains digits
    ArrayList<Integer> numbers = new ArrayList<Integer>(); // will contain digits converted to numbers when leaf node is hit
    int sum = 0;
    public int sumNumbers(TreeNode root) {
        
        populateNumbers(root);
        
        for (int value:numbers) {
            sum +=value;    
        }
         
        return sum;
    }
    
    
    public void populateNumbers(TreeNode root) {
        if(root == null) {
            return;
        }
    
        nodes.add(root.val);  // In preorder traversal you will print here add the digit to the node;
    
        if (root.left == null && root.right == null) { // you have hit the leaf node
    
            int sum =0;
            for (int x :nodes) {
                //System.out.println("inondes :"+x);
                sum = sum*10+x;
            }
            // collect the digits in the array and make it a number
            numbers.add(sum);
            return;
        }
        
        populateNumbers(root.left);   //call with root.left 
        if (root.left != null) { 
            nodes.remove(nodes.size()-1); // you remove the leaf you added from the arraylist
        }
        populateNumbers(root.right); // call with root.right
        if (root.right != null) {
            nodes.remove(nodes.size()-1); // you remove the leaf you added from the arraylist
        }
    }
    }

Log in to reply
 

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