Clarification - Only add the sum of those nodes whose both child nodes are NULL.


  • 2
    W

    The question clearly specifies that any number made from root to any leaf should be counted. So for the test case {1, 0} the correct ans should be 11 -- 10 + 1 as 1 has one child and one leaf.
    But the OJ accepts solutions where leafs are those nodes which have no children at all, so for the above case expected answer is 10.

        /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int sumNumbers(TreeNode *root) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            sum = 0;
            if(root)
                getSum(0,root) ;
            return sum ;
        }
    private:
        int sum ;
        void getSum(int num, TreeNode *root){
            num = num*10 + root->val ;
            if(root->left)
                getSum(num,root->left) ;
            if(root->right)
                getSum(num,root->right) ;
            if(!root->left && !root->right){        
                sum += num ;
            }
    /*      if(!root->left || !root->right){        // this is the right solution
                sum += num ;
            }
    */
            return ;
        }
    };

  • 2

    From Wikipedia's Definitions for rooted trees:

    A leaf node has no children.

    If you look at the tree {1,0}:

      1
     /
    0
    

    It is obvious that the node 1 is not a leaf node.


Log in to reply
 

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