Can you improve this algorithm?


  • 54
    P
    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public int sumNumbers(TreeNode root) {
            if (root == null)
                return 0;
            return sumR(root, 0);
        }
        public int sumR(TreeNode root, int x) {
            if (root.right == null && root.left == null)
                return 10 * x + root.val;
            int val = 0;
            if (root.left != null)
                val += sumR(root.left, 10 * x + root.val);
            if (root.right != null)
                val += sumR(root.right, 10 * x + root.val);
            return val;
        }
    }

  • 0
    S
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 3
    S

    I did it in almost the same way in C++ and I guess it cannot be optimized further. We have to visit each element once, atleast, and thats what our algorithm does.

    Pasting my solution:

    class Solution {
    private:
    	void traverseAndSum(TreeNode *root, int &sum, int parSum);
    public:
    	int sumNumbers(TreeNode *root) {		
    		int sum = 0;
    		traverseAndSum(root, sum, 0);
    		return sum;
    	}
    };
    
    void Solution::traverseAndSum(TreeNode *root, int &sum, int parSum)
    {
    	if (root == NULL)
    		return;
    
    	parSum = parSum * 10 + root->val;
    	if (root->left == NULL && root->right == NULL)
    	{
    		// Encountered a leaf node. Evaluate the sum
    		sum += parSum;
    		return;
    	}
    	traverseAndSum(root->left, sum, parSum);
    	traverseAndSum(root->right, sum, parSum);
    }

  • 1

    Same idea in iterative version.

    int sumNumbers(TreeNode *root) {
        int sum = 0;
        if(root == NULL) return sum;
        stack<TreeNode *> array;
        stack<int> val;
        array.push(root);
        val.push(0);
        while(!array.empty()){
            TreeNode *node = array.top();
            int prev = val.top();
            array.pop();
            val.pop();
            while(node->left != NULL){
                int cur = prev*10 + node->val;
                if(node->right != NULL){
                    array.push(node->right);
                    val.push(cur);
                }
                prev = cur;
                node = node->left;
            }
            int cur = prev*10 + node->val;
            if(node->right == NULL){
                sum += cur;
            }else{
                array.push(node->right);
                val.push(cur);
            }
        }
        return sum;
    }

  • 14
    P

    I prefer the iterative method over recursion. I used 2 queues to do a breadth first traversal. both time and space complexity is O(N):

    public class Solution {
    public int sumNumbers(TreeNode root) {
        int total = 0;
        LinkedList<TreeNode> q = new LinkedList<TreeNode>();
        LinkedList<Integer> sumq = new LinkedList<Integer>();
        if(root !=null){
            q.addLast(root);
            sumq.addLast(root.val);
        }
        while(!q.isEmpty()){
            TreeNode current = q.removeFirst();
            int partialSum = sumq.removeFirst();
            if(current.left == null && current.right==null){
                total+=partialSum;
            }else{
                if(current.right !=null){
                    q.addLast(current.right);
                    sumq.addLast(partialSum*10+current.right.val);
                }
                if(current.left !=null){
                    q.addLast(current.left);
                    sumq.addLast(partialSum*10+current.left.val);
                }
                
            }
            
        }
        return total;
    }
    

    }


  • 0
    I
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    I

    Sorry, I forgot to add some explanation. I add some explanations, my English is poor, thanks for your comments.:)

    class Solution {
    public:
    int sumNumbers(TreeNode *root)
    {
    if (!root)
    return 0;

        vector<TreeNode*> sta;	// this is a vector to hold the nodes from root to a leaf. (Why not stack? Because when calculate the sum the vector is more easy than stack)
        stack<bool> status;	// in PostOrder Traversal, the value of this stack represents the node whether should be pop.(false not pop, true pop)
        TreeNode *top;
        int temp, sum = 0;
    
        while (root || !sta.empty())	// PostOrder Traversal
        {
            if (root)			// Node is non-empty push into vector, and push false in stack
            {
                sta.push_back(root);
                status.push(false);
                root = root->left;	// deep into left
            }
            else			// node is empty, consider whether the node should be pop
            {
                top = sta[sta.size() - 1]; // the top of the vector(equals to the top() function of stack STL)
                if (!status.top())	   // if top of stack is fasle, change false to true, and change the node to the right
                {
                    status.pop();
                    status.push(true);
                    root = top->right;
                }
                else			// the node should be pop
                {
                    if (!top->left && !top->right)	// the node is a leaf, 
                    {	
                        temp = 0;
                        for (int i = 0; i < sta.size(); i++) 	// calculate the sum of vector (repersents the sum of root to this leaf)
                            temp = 10 * temp + sta[i]->val;
                        sum += temp;
                    }
                    sta.erase(sta.end() - 1);	// delete the "top one" of the vector
                    status.pop();
                    root = NULL;
                }
            }
        }
    
        return sum;
    }
    

    };


  • 0
    S

    Hi @ikimk, thanks for your updating. Sorry to make this misunderstand. I mean it could be better to post this excellent code as an answer, not as a comment like what it is right now.


  • 8
    V
    int sumNumbers(TreeNode *root) {
    	return sumNumber(root);
    }
    
    /*levelBase - holds number upto current level excluding nodes value. 
    For example, if the number upto current node is 1239, then levelBase will have 1230.*/
    int sumNumber(TreeNode *root, int levelBase=0) {
    	if(root == 0)
    		return 0;
    	if(root->left == 0 && root->right == 0) {
    		return levelBase + root->val; 
    	}
    	int nextLevelBase = (levelBase + root->val) *10 ;
    	int leftSubTreeSum = sumNumber(root->left, nextLevelBase);
    	int rightSubTreeSum = sumNumber(root->right, nextLevelBase);
    
    	return leftSubTreeSum + rightSubTreeSum;
    }
    

  • 4
    U

    We can do it without helper function.

    class Solution:
    # @param root, a tree node
    # @return an integer
    def sumNumbers(self, root):
        if not root:
            return 0
        if not root.left and not root.right:
            return root.val
        val = 0
        if root.left:
            root.left.val += root.val * 10
            val += self.sumNumbers(root.left)
            root.left.val -= root.val * 10
        if root.right:
            root.right.val += root.val * 10
            val += self.sumNumbers(root.right)
            root.right.val -= root.val * 10
        return val

  • 0
    C

    The reason you don't need helper function is that you change the node's value, which I think it's not a good way to solve this problem. It is better not change the input.


  • 0
    A

    My iterative solution, hope it's easy to understand. its space complexity is O(h), where h is the maximum height of the tree.

    It traverse the tree in Post-Order. when traverse the tree, 'cur' point to the current node, 'pre' point to the last accessed node. There are only 3 cases: pre is cur's parent, pre is cur's left, child, pre is cur's right child.

    for details, you can refer to http://leetcode.com/2010/10/binary-tree-post-order-traversal.html

    int sumNumbers(TreeNode *root) {
    	if (root == nullptr){
    		return 0;
    	}
    	
    	stack<TreeNode*> stk;
    	TreeNode* pre = nullptr;
    	stk.push(root);
    	int sum = 0;
    	int number = 0;
    
    	while (!stk.empty()){
    		TreeNode* cur = stk.top();
    
    		// we are traversing down the tree
    		if (!pre || (pre->left == cur) || (pre->right == cur)){
    			number = number * 10 + cur->val;
    			if (cur->left){
    				stk.push(cur->left);
    			}
    			else if (cur->right){
    				stk.push(cur->right);
    			}
    			else {
    				sum += number;
    				number /= 10;
    				stk.pop();
    			}
    		}
    		// we are traversing up the tree from the left
    		else if (cur->left == pre){
    			if (cur->right){
    				stk.push(cur->right);
    			}
    			else{
    				stk.pop();
    				number /= 10;
    			}
    		}
    		// we are traversing up the tree from the right
    		else{
    			stk.pop();
    			number /= 10;
    		}
    		pre = cur;						
    	}
    
    	return sum;
    }

  • 0
    T

    According to potpie, I have a very simple solution:

    int sumNumbers(TreeNode *root) {
    	return sumNumbers_helper(root,0);
    }
    int sumNumbers_helper(TreeNode *root, int s) {
        if (root == NULL) return 0; // root is NULL then return 0
    	s = s*10 + (root -> val);	// current sum times 10 plus root value
    	if (root->left == NULL && root->right == NULL) return s;	//both left and right are NULL, return sum
    	return sumNumbers_helper(root->left,s) + sumNumbers_helper(root->right,s); // recursively call the helper with sum
    }
    

  • 0
    N

    How about post order travel with two stack. It should be O(N) complicit and O(level of binary tree) space.

    public int sumNumbers(TreeNode root) {
        int result = 0;
        if (root != null) {
            Deque<Integer> dataStack = new ArrayDeque<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode node = root;
            TreeNode lastVisited = null;
            while (!stack.isEmpty() || node != null) {
                if (node != null) {
                    int t = dataStack.isEmpty() ? 0 : dataStack.peek();
                    t = t * 10 + node.val;
                    if (node.left == null && node.right == null) {
                        result += t;
                    }
                    stack.push(node);
                    dataStack.push(t);
                    node = node.left;
                } else {
                    TreeNode peek = stack.peek();
                    if (peek.right != null && peek.right != lastVisited) {
                        node = peek.right;
                    } else {
                        stack.pop();
                        dataStack.pop();
                        lastVisited = peek;
                    }
                }
            }
        }
        return result;
    }
    

  • 0
    V

    I use this algorithm too.


  • 0
    M

    Thanks for sharing. Could you tell why you prefer iterative method?


  • 0
    G

    Hi ted7726,
    I think you have the best solution with least number of lines of code possible. I wanted to give it a thumbs up or the vote but can't cause its already in a reply.. If you have posted it somewhere else, please do tell me, I will add my vote.
    Thanks.


  • 0
    J

    Actually, your algorithm is depth-first-search, not breadth-first-search. For example, although root->right is pushed into stack right after root is visited, but it will be visited after root's whole left sub-tree is visited.


Log in to reply
 

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