Recursive and iterative(level-order traversal) solution in C++,easy to uns understand


  • 0
    V

    Solution (1):

    class Solution {
    public:
        bool hasPathSum(TreeNode* root, int sum) {
            if (root == NULL) 
                return false;
            
            if (root->left == NULL && root->right == NULL)
                if (root->val == sum)
                    return true;
                else
                    return false;
            
            return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
        }
    };
    

    Solution (2):

    class Solution {
    public:
        bool hasPathSum(TreeNode* root, int sum) {
            queue<TreeNode *> q;//here you can use stack alternatively
            TreeNode *temp = NULL;
            int add = 0;
            
            if (root == NULL) return false;
            q.push(root);
            
            while (!q.empty())
            {
                temp = q.front();
                q.pop();
                if (temp->left != NULL)
                {
                    temp->left->val += temp->val;
                    q.push(temp->left);
                }
                if (temp->right != NULL)
                {
                    temp->right->val += temp->val;
                    q.push(temp->right);
                }
                if (temp->left == NULL && temp->right == NULL && temp->val == sum)
                        return true;
            }
            
            return false;
        }
    };

  • 0

    This is BFS right? But good idea to add the parent val to the children!


  • 0
    V

    u could take it as BFS or level-order traversal,it's all ok


Log in to reply
 

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