关于非递归的疑问
来源：1-12 二分搜索树的层序遍历
qq_慕莱坞4316410
2022-04-27 15:35:43
啵啵老师，就是学到这里，我发现无论是那种方式非递归的方式，都会创建一个node，用这个新创建的node去指向左子树或者右子树，这个创建node的过程会不会额外的开辟一个空间啊，递归的话好像没有这一步操作，不知道是不是自己理解不够。
写回答
1回答
-
你所说的“新创建的 Node” 没有开辟存储元素的新空间，你所说的这个“新创建的 Node”，只是一个引用，指向已经创建好的空间（树上的节点）。表现在没有 new 操作。创建一个新的引用的性能消耗不是 concern，他和新创建一个 int 本质是一样的。（因为一个引用就是一个地址，一个地址就是一个 int）。
从另一个角度，递归的操作也有这个“消耗”。以先序遍历为例，函数声明是：
private void preOrder(Node node)
这个函数声明的参数就是一个 Node，在递归中不断调用这个函数的时候，传进来参数 Node，在每一次函数调用的时候，这个参数就要“复制一次”（注意，只是复制引用，而不是整个内存空间的复制）。它的本质就是：新一层的参数 node = 之前一层的 node.left 或者 node.right，也是这样的一个引用变量的复制。
你的这个问题很重要，看似是在关注性能问题，但本质其实是：到底什么是引用，什么是真正的开空间。简单来说，Java 中的引用，就是 C/C++ 中的指针，请仔细体会一下这个概念，这是非常非常重要的。
继续加油！：）
0
相似问题