LeetCode从前序与中序遍历构造二叉树时rootIdx为何要传引用？

前提逻辑 #

前序遍历的顺序为「根→左子树→右子树」，这段代码的核心逻辑就是严格按照preorder数组的顺序，依次取出元素作为每棵子树的根节点，rootIdx的作用就是标记当前取到了preorder数组的哪个位置。

引用传递的作用 #

使用引用传递时，所有递归调用的函数共用同一个rootIdx变量：

• 每次取preorder[rootIdx]作为当前根节点后，执行rootIdx++，这个改动会同步到所有递归层级
• 左子树的全部递归处理完成后，rootIdx刚好已经走到了右子树根节点在preorder中的位置，直接就能给右子树的递归逻辑使用，完全符合前序遍历的访问顺序。

按值传递失败的原因 #

如果改成按值传递，每个递归函数拿到的都是rootIdx的独立副本，内层递归对rootIdx的修改不会影响外层：
举个简单的测试用例说明，假设preorder为[3,9,20,15,7]，inorder为[9,3,15,20,7]：

1. 最外层调用拿到rootIdx=0，取preorder[0]=3作为根，把自己的副本加1变成1，接着调用左子树递归
2. 左子树递归拿到值为1的副本，取preorder[1]=9作为根，把自己的副本加1变成2，左子树没有子节点，递归结束返回最外层
3. 此时最外层的rootIdx副本还是1，调用右子树递归时还是传1，会错误地取preorder[1]=9作为右子树的根，完全不符合逻辑，最终运行失败。

内容的提问来源于stack exchange，提问作者Nishant Sagar