java - 两个函数的区别

Question

我有一个关于递归函数和更新函数参数的问题。也就是说，我有两个功能:

public static void populateArray(int[]level,Node root,int currentLevel) {

    currentLevel++;
    if(root.left!=null) {
        populateArray(level,root.left,currentLevel);
    }
    level[currentLevel]++;
    if(root.right!=null) {
        populateArray(level,root.right,currentLevel);
    }

}

public static void populateArray2(int[]level,Node root,int currentLevel) {

        if(root.left!=null) {
            currentLevel++;
            populateArray2(level,root.left,currentLevel);
        }
        level[currentLevel]++;
        if(root.right!=null) {
            currentLevel++;
            populateArray2(level,root.right,currentLevel);
        }

    }

这些函数应该用二叉树中每一层的节点数填充一个空数组。我认为这些函数的工作方式相同，但事实证明，第一个函数正确执行该任务，而第二个函数则不然，也就是说，从递归调用返回后， currentLevel 没有更新第二个函数，我很好奇为什么会这样？我认为在这两个函数中，当我们从递归调用返回时，参数将自动更新(第一个函数的情况如何)。仅当每次递归调用后我们放置 currentLevel-- 时，第二个函数才会起作用。有人可能知道为什么会发生这种情况吗？预先感谢您!

Answer 1

在populateArray2中，您首先访问level[currentLevel]++，然后才将currentLevel增加1，如果root.right!= null。

我在您的代码中添加了一些注释以突出显示差异:

public static void populateArray(int[]level,Node root,int currentLevel) {
    currentLevel++; // Increase currentLevel by 1 first
    if(root.left!=null) {
        populateArray(level,root.left,currentLevel);
    }
    level[currentLevel]++; // Increase level by 1 after that
    if(root.right!=null) {
        populateArray(level,root.right,currentLevel);
    }
}

public static void populateArray2(int[]level,Node root,int currentLevel) {
    if(root.left!=null) {
        currentLevel++;
        populateArray2(level,root.left,currentLevel);
    }
    level[currentLevel]++; // Increase level by 1 first
    if(root.right!=null) {
        currentLevel++; // Increase currentLevel by 1 after that
        populateArray2(level,root.right,currentLevel);
    }
}

这就是这里的关键区别，因为增加了不同的级别，所以导致了不同的结果。

此外，如果 root.left 和 root.right 都不为 null，则您已在您的代码中执行了两次 currentLevel++ populateArray2 方法也是如此。

我不确定您想使用 populateArray2 实现什么目的，但我会删除它并坚持使用原来的 populateArray-方法..

<小时/>

编辑:正如@Simon所提到的，我只解决了两个populateArray方法之间的差异，就像OP的问题一样。我没有提到针对他的要求的实际修复。

See @Simon's answer below for an actual fix following those requirements.