Problem Link:
https://leetcode.com/problems/path-sum/
(It is also problem of day for 04-10-2022)
Solutions:
=========================================================================
Solution 1:
class Solution {
public static void fun(TreeNode root, int sum , int val, ArrayList<Integer>aa){
if(root==null){
return ;
}
else if(root.left==null && root.right==null){
val=val+root.val;
aa.add(val);
return ;
}
else{
fun(root.left,sum,val+root.val,aa);
fun(root.right,sum,val+root.val,aa);
}
}
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null){
return false;
}
else{
ArrayList<Integer>aa=new ArrayList<Integer>();
fun(root,sum,0,aa);
// System.out.println(aa);
if(aa.contains(sum)){
return true;
}
return false;
}
}
}
Time Complexity: O(N)[N=number of nodes in tree][1ms faster than 69.13%]
Space Complexity: O(N)[A tree with n nodes is given][43.9 Mb less than 16.57%]
Auxiliary Space: O(N)[ArrayList data structure is used for storing.]
Approach Used:
Variable declared here and their relevance is:
int target: given target value with whom we need to compare with the value. (in question only)
In the solution, the target will be referred to as the sum.
int val: this refers to the sum of node's data at different levels while traversing.
Here we will traverse the whole tree and while traversing we will calculate the value of val once we reach to leaf node then we will store that value in ArrayList.
After traversing the whole tree we will get the ArrayList consisting of all path sum values of different paths present in the tree and later we will use contains the function to see whether the ArrayList contains the value of the target or not.
If it contains the target value we will return true
else we will return false.
How we will identify that we have reached the leaf node?
The leaf node is where the right child and left child of that node are both nulls.
and we will also increment the val parameter with the node data as it will be the last node and its right and left child are both nulls.
so thats why inside root.left==null && root.right==null condition
we add first val=val+root.val
beacuse now root.left.val==not exist and root.right.val==null as node themeselves dont exist so as their data wont exist too.
=========================================================================
Solution 2:
class Solution {
boolean status=false;
public void fun(TreeNode root, int sum, int s, boolean status){
if(root==null){
return;
}
else if(root.left==null && root.right==null){
s=s+root.val;
if(s==sum){
this.status=true;
}
}
else{
fun(root.left,sum,s+root.val,status);
fun(root.right,sum,s+root.val,status);
}
}
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null){
return false;
}
else{
fun(root,sum,0,status);
if(status==true){
return true;
}
return false;
}
}
}
Time Complexity: O(N)[N=number of nodes in tree][1ms faster than 69.13%]
Space Complexity: O(N)[A tree with n nodes is given][43.9 Mb less than 42.57%]
Auxiliary Space: O(1)[No ArrayList or any other data structure is used for storing.]
Approach Used:
Variable declared here and their relevance is:
int target: given target value with whom we need to compare with the value. (in question only)
In the solution, the target will be referred to as the sum.
int s: this refers to the sum of node's data at different levels while traversing.
boolean status: It is a boolean variable that is global and will be accessed globally. It is similar to a flag and will become true once it gets the target sum in the tree otherwise will remain false.
Here we will traverse the whole tree and while traversing we will calculate the value of val once we reach to leaf node then we will compare that value with the sum variable.
If that value matches with the sum variable then make status to be true.
How we will identify that we have reached the leaf node?
The leaf node is where the right child and left child of that node are both nulls.
and we will also increment the val parameter with the node data as it will be the last node and its right and left child are both nulls.
so thats why inside root.left==null && root.right==null condition
we add first val=val+root.val
beacuse now root.left.val==not exist and root.right.val==null as node themeselves dont exist so as their data wont exist too.
Moreover why we have used
this.status=true
Can't we use simply status=true?
The answer is tree calls are recursive in nature. It means once you call for a left child then you go for the right child and then control goes back to the parent and the same process continues.
While during this process one thing to note is that variables' values get redo after the end of their call.
For example, suppose while calling for root.left you get the desired value so you make stauts=true
now when you will go for root.right it will be restored back to its previous stage what it was at the time of the function call and since you are comparing at the leaf stage and then making decisions and changing the status flag too so before that stage or level mostly it will be false.
So again status becomes false and hence while calling for the right child it will remain false.
In such a manner you won't get the correct answer.
So for removing that issue we have declared the status flag as global and it will be accessible by all calls but to make that status value true only we have used this keyword(as both variables name same in function calls also and the global variable also so as to create a distinction between them we use this keyword and make global status flag as true)
and later return that status flag.
=========================================================================
Solution 3:
class Solution {
boolean status=false;
public void fun(TreeNode root, int sum,int s){
if(root==null){
return;
}
else if(root.left==null && root.right==null){
s=s+root.val;
if(s==sum){
status=true;
}
}
else{
fun(root.left,sum,s+root.val);
fun(root.right,sum,s+root.val);
}
}
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null){
return false;
}
else{
fun(root,sum,0);
if(status==true){
return true;
}
return false;
}
}
}
Time Complexity: O(N)[N=number of nodes in tree][1ms faster than 69.13%]
Space Complexity: O(N)[A tree with n nodes is given][43.9 Mb less than 51.42%]
Auxiliary Space: O(1)[No ArrayList or any other data structure is used for storing.]
Approach Used:
The same approach is described in the second solution, however here we have not passed status as a parameter in function calls.
The reason is quite simple as it is global so it can be accessed from anywhere and anywhere in code, so once your s becomes equal to target you directly make the status flag as true.
No need of using this keyword and there is no other parameter with which you want to distinguish the status flag
So simply use the status flag and return it later.
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
-----------------------------------------------------------------------------------------------------------------------------
Comments
Post a Comment