Can you improve this algorithm?

Question

/**
 * 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;
    }
}

Comments

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;
}

};

---

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.

Answer 1

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);
}

Answer 2

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;
}

Answer 3

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;
}

}

Answer 4

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;
}