递归中的变量被重置。有人可以解释如何吗？

Question

我正在尝试从 Leetcode 中解决这个问题 https://leetcode.com/problems/count-good-nodes-in-binary-tree/

这是我的解决方案：我不明白为什么这个递归 root.left 节点的计数值在遍历 root.right 时不成立。据我了解，我是

检查当前节点是否良好并更新计数和列表
遍历左节点更新计数
上面的计数应该在遍历右节点时进入右节点并更新计数值但它没有发生

为什么这不起作用。我知道正确的解决方案只是不能真正理解递归如何重置我的计数变量

    /**
     * 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);
           
       }
    }

Answer 1

如果您需要“pass-by-reference”语义，您可以使用大小为 1 的 AtomicInteger 或 int[] 而不是 int。

Answer 2

preorderGoodNodes 的递归调用不会看到参数 count 的更新：它基本上是一个局部变量。该值及其任何更改仅在当前方法调用期间有效，并且在将其值传递给递归调用时不会进行更改。

但是方法目前是void：而不是传递count，return它：

// 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;
}

然后，在您的 goodNodes 方法中：

return preorderGoodNodes(root,list,treeroot);

Answer 3

谢谢大家的回答。每个答案都帮助我理解。我了解到问题不是我对递归调用的理解，而是我是按值而不是按引用发送变量的事实。

当我将 int 转换为 int[] 进行计数时，这段代码对我有用。请记住解决这个问题的标准方法是返回 int 而不是 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);
       
   }
}

递归中的变量被重置。有人可以解释如何吗？

variables in recursion get reset. Can someone explain how?

java

recursion

tree

binary-tree