在递归调用期间，方法的参数如何存储在堆栈中？

Question

我在做一道 leetcode 题 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/，我对在递归调用期间如何存储方法的参数感到困惑。

如果访问了一个节点，我想保存它被访问时的状态。当我发送两个变量时，当堆栈展开时，更新的变量值将丢失。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        boolean val1 = false, val2 = false;
        System.out.println("val1 - "+val1+" val2 - "+val2);
        System.out.println();

        TreeNode node = lca(root, p, q, val1, val2);
        System.out.println();
        System.out.println("val1 - "+val1+" val2 - "+val2);

        if(val1==true && val2==true)
            return node;
        return null;
    }
    
    private TreeNode lca(TreeNode root, TreeNode p, TreeNode q, boolean val1, boolean val2) {
        if(root==null) 
            return root;
        else if( p==root){
            val1 = true;
            System.out.println("val1 - "+val1+" val2 - "+val2);
            return root;
        } 
        else if( root==q){
            val2 = true;
            System.out.println("val1 - "+val1+" val2 - "+val2);
            return root;
        } 

        TreeNode left = lca(root.left, p, q, val1, val2);
        TreeNode right = lca(root.right, p, q, val1, val2);
        
        if(left==null && right==null) return null;
        else if(left==null) return right;
        else if(right==null) return left;
        else return root;
    }
}

Output -
val1 - false val2 - false

val1 - true val2 - false
val1 - false val2 - true

val1 - false val2 - false

但是，如果我发送一个数组并更新数组内的值，并在递归期间将数组本身作为参数传递，那么更新后的变量值将被保留。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        boolean res[] = new boolean[2];
        //boolean val1 = false, val2 = false;
        System.out.println("val1 - "+res[0]+" val2 - "+res[1]);
        System.out.println();

        TreeNode node = lca(root, p, q, res);
        System.out.println();
        System.out.println("val1 - "+res[0]+" val2 - "+res[1]);

        if(res[0]==true && res[1]==true)
            return node;
        return null;
    }
    
    private TreeNode lca(TreeNode root, TreeNode p, TreeNode q, boolean res[]) {
        if(root==null) 
            return root;
        else if( p==root){
            res[0] = true;
            System.out.println("val1 - "+res[0]+" val2 - "+res[1]);
            return root;
        } 
        else if( root==q){
            res[1] = true;
            System.out.println("val1 - "+res[0]+" val2 - "+res[1]);
            return root;
        } 

        TreeNode left = lca(root.left, p, q, res);
        TreeNode right = lca(root.right, p, q, res);
        
        if(left==null && right==null) return null;
        else if(left==null) return right;
        else if(right==null) return left;
        else return root;
    }
}

Output - 

val1 - false val2 - false

val1 - true val2 - false
val1 - true val2 - true

val1 - true val2 - true

我觉得我在这里缺少一些基本知识，任何人都可以帮助我理解这两个代码有何不同以及任何material我可以阅读以提高我在堆栈和递归方面的知识吗？

Answer 1

这个问题与“递归”关系不大，而与函数调用本身有关。

当您调用 foo(var1, var2) 时，变量得到 passed by value。您在函数块内所做的更改不会传播到函数外。

当你传递数组时，它得到passed by reference/指针。对其进行的任何修改都是对它的实际内存进行的，因此即使在功能块之外，更改也会 retained/reflected。

您可以详细了解按值传递和引用传递之间的区别 here。

编辑：
Java 是“始终”pass-by-value 因为对象具有按值传递的引用。 here 详细阐明了这个令人困惑的术语。

在递归调用期间，方法的参数如何存储在堆栈中？

How does parameters of a method get stored in stack during a recursive call?

java

algorithm

tree

recursion

data-structures