How to get the correct answer without changing the values in the tree?


  • 2
    J
    class Solution {
    public:
        bool hasPathSum(TreeNode *root, int sum) {
            queue<TreeNode *> q;
            if(root!=NULL)
                q.push(root);
            while(!q.empty()){
                TreeNode *cur = q.front();
                if(cur->left==NULL&&cur->right==NULL)
                {   
                    if(cur->val == sum)
                        return true;
                }
                if(cur->left!=NULL){
                cur->left->val+=cur->val;
                q.push(cur->left);
                }
                if(cur->right!=NULL){
                cur->right->val+=cur->val;
                q.push(cur->right);
                }
                q.pop();
            }
            return false;
        }
    };
    

    Here is my code using BFS. It works but it also changes the values of the binary tree. What am I supposed to do if I don't want to change the values?


  • 0
    R
    class Solution {
    public:
    bool hasPathSumUtil(TreeNode *root, int cur_sum, int sum)
    {
        if(root)
        {
            if(!root->left && !root->right)
             {
                 if(cur_sum+root->val==sum)
                 return true;
                 else
                 return false;
             }
            return hasPathSumUtil(root->left,root->val+cur_sum,sum)|| hasPathSumUtil(root->right,root->val+cur_sum,sum);
        }
        return false;
    }
        bool hasPathSum(TreeNode *root, int sum) {
            int cur_sum=0;
            return hasPathSumUtil(root,cur_sum,sum);
            
        }
    };
    

    No need to change the values of the node . You can take a local variable "cur_sum" which is used to store the sum up to the current node using preorder traversal. If the current node is a leaf node, we compare the cur_sum's value with the given sum. If yes, we return true, else, we try an alternate path


  • 26
    M

    ruparel's answer is technically correct, but also makes things more complicated than they need to be. Using a DFS, you can search down to the leaves and see if any of the paths result in the sum. As an int is a primitive data type, passing it as a parameter will copy it, and any changes will not be transferred back up the tree. Therefore, you do not need to leave the sum alone.

    At each node, subtract the value of the node from the sum. If the node is a leaf, return whether the sum at that point is 0 (the path from root to leaf has decreased from its original to 0, meaning the path sum is the original value). If it is not a leaf, pass it further down the tree with the new sum. If a node is null, return false since either the prior node was not a leaf and so cannot be the end of the path, or the entire tree is null.

    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        
        sum -= root.val;
        if(root.left == null && root.right==null)  return sum == 0;
        else return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
    }

  • 0
    J

    Nice answer! Thank you!


  • 1
    T

    In each call stack, this function should return true if the sum of the left subtree OR the sum of the right subtree is equal to the original sum subtract the values of all the ancestors, hence this is my recursive step. The base cases are that if I get to a null node, in which it should return false, and if I get to a leaf and the overall sum adds up, I return true.

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

  • 0
    P

    This is my Java solution. It's basically a Depth-First Search, and as you can see, it can be implemented very easily using recursion.

    Cheers.

    public class Solution {
        public boolean hasPathSum(TreeNode root, int sum) {
            if(root==null)  return false;
            
            if(root.val==sum && root.left==null && root.right==null)    return true;
            else {
                return (hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val));
            }
            
        }
    }

  • 3
    R

    You can use another queue.

    public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
    	if (root==null) return false;
    	Deque<Integer> sum_queue = new LinkedList<Integer>();
    	Deque<TreeNode> node_queue=new LinkedList<TreeNode>();
    	sum_queue.addFirst(root.val);
    	node_queue.addFirst(root);
    	while(!node_queue.isEmpty()){
    		TreeNode node=node_queue.pollFirst();
    		int num=sum_queue.pollFirst();
    		if (node.left==null&&node.right==null){
    			if (num==sum) return true;
    		}
    		if (node.left!=null){
    			node_queue.addLast(node.left);
    			sum_queue.addLast(node.left.val+num);
    		}
    		if (node.right!=null){
    			node_queue.addLast(node.right);
    			sum_queue.addLast(node.right.val+num);
    		}
    	}
    	return false;
    }
    

    }


  • 0
    S

    your method is BFS, yes?


  • 0
    Z

    here is a java code.

        public boolean hasPathSum(TreeNode root, int sum) {
            if (root == null)
                return false;
            if (root.left == null && root.right == null)
                return root.val == sum;
            return hasPathSum(root.left, sum - root.val)
                    || hasPathSum(root.right, sum - root.val);
        }

Log in to reply
 

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