I am trying to solve this question from Leetcode https://leetcode.com/problems/count-good-nodes-in-binary-tree/

This is my solution: I am not able to understand why is this recursion the count value from root.left node does not hold up when traversing the root.right . In my understanding I am

1. Checking if current node is good or not and updating count and list
2. Traversing the left node to update count
3. Above count should go into right node while traversing right node and update the count value but its not happening

Why is this not working. I know the correct solution just cant really understand how recursion resets my count variable

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public int goodNodes(TreeNode root) {
            int count = 0;
            List<Integer> list = new ArrayList<>();
            TreeNode treeroot = root;
            preorderGoodNodes(root,list,count,treeroot);
            return count; 
        }
        
       public void  preorderGoodNodes(TreeNode root,List<Integer> list,int count,TreeNode treeroot)
       {
        
           if(root==null) // check if root is null
               return;
           
           // if current node is actual root of the tree then count    since root is always good
           //also add the root to the list
           if(treeroot ==root) 
           {
               count  ;
               list.add(root.val);
           }
           else
               // if node is not the root then check if it is good or not by looking into the list
           {  
                   int flag = 0;
                   for(int x : list) //looking into the list
                   {
                       if(x>root.val)
                       {
                           flag = 1;
                           break;
                       }
    
                   }
    
                   if(flag==0) // if it is good count  
                           count  ;
                       
               list.add(root.val); // weather good or not add to the list
    
           }
           
           List<Integer> rightlist = new ArrayList<>(list); 
           // make a copy of the list to send to right node 
           //because count and list from left tree should not effect right tree
           
           preorderGoodNodes(root.left,list,count,treeroot);
**// why does count reset after this line ??**
           preorderGoodNodes(root.right,rightlist,count,treeroot);
           
       }
    }

CodePudding user response：

If you need "pass-by-reference" semantic you can use AtomicInteger or int[] of size 1 instead of int.

CodePudding user response：

Recursive calls of preorderGoodNodes won't see updates to the parameter count: it's basically a local variable. The value and any changes to it only live for as long as the current method invocation, and changes are not made when its value is passed to the recursive call.

But the method is currently void: instead of passing count, return it:

// No count parameter, return type now int
public int  preorderGoodNodes(TreeNode root,List<Integer> list,TreeNode treeroot) {
  int count = 0;

  // ...

  count  ;

  // ...

  count  = preorderGoodNodes(root.left,list,treeroot);
  count  = preorderGoodNodes(root.right,rightlist,treeroot);

  return count;
}
       

Then, in your goodNodes method:

return preorderGoodNodes(root,list,treeroot);

CodePudding user response：

Thanks for all the answers. Each answer helped me in my understanding. I was able to learn that the problem was not my understanding of the recussive calls but the fact that i was send variable by value and not by reference.

This code worked for me when i made int into int[] for count. Please bear in ming that the standard way to solve this is by returning int instead of void

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int goodNodes(TreeNode root) {
        int[] count = new int[1];
        count[0]=0;
        List<Integer> list = new ArrayList<>();
        list.add(root.val);
        TreeNode treeroot = root;
        preorderGoodNodes(root,list,count,treeroot);
        return count[0]; 
    }
    
   public void  preorderGoodNodes(TreeNode root,List<Integer> list,int[] count,TreeNode treeroot)
   {
    
       if(root==null) // check if root is null
           return;
       
       // if current node is actual root of the tree then count    since root is always good
       //also add the root to the list
       if(treeroot ==root) 
       {
           count[0]  ;
           list.add(root.val);
       }
       else
           // if node is not the root then check if it is good or not by looking into the list
       {  
               int flag = 0;
               for(int x : list) //looking into the list
               {
                   if(x>root.val)
                   {
                       flag = 1;
                       break;
                   }

               }

               if(flag==0) // if it is good count  
                      count[0]  ;
                   
           list.add(root.val); // weather good or not add to the list

       }
       
       List<Integer> rightlist = new ArrayList<>(list); 
       // make a copy of the list to send to right node 
       //because count and list from left tree should not effect right tree
       
       preorderGoodNodes(root.left,list,count,treeroot);
       preorderGoodNodes(root.right,rightlist,count,treeroot);
       
   }
}