Java链表实现二叉树插入时为什么需要使用临时节点？

原理说明 #

你遇到的根节点丢失问题，本质是直接修改了存储根节点地址的成员变量root本身，导致原始根节点的引用丢失。

Java中TreeNode属于引用类型，类成员变量private TreeNode root存储的是根节点对象在堆内存中的地址，而非节点对象本身：

• 第一次插入节点50时，root正确存储了50节点的内存地址，树结构正常
• 第二次插入节点10时，树高为1（奇数），进入左子树插入逻辑，你在遍历的时候直接执行root = root.left，遍历结束后root存储的地址就从原来的50节点变成了新插入的10节点，原始根节点的引用被直接覆盖丢失
• 后续所有插入、遍历操作都是基于已经被篡改的root执行，自然无法再找到原来的根节点50

current_node的作用 #

current_node是你创建的根节点引用的临时副本：
你仅把root中存储的根节点地址复制给了这个临时变量，遍历过程中修改的只是临时变量存储的地址值，完全不会改动成员变量root本身存储的根节点地址，因此根节点的引用会一直被保留，不会丢失。

简单类比：root相当于你手机里存储的家庭地址，current_node相当于你出门前抄在便签上的地址副本，你照着便签找路、在便签上修改路线，都不会影响你手机里存的原始家庭地址，你随时可以通过手机里的地址找到家。如果不用副本直接改手机里的地址，改完之后你自然找不到原来的家了。

内容的提问来源于stack exchange，提问作者Rishabh Tiwari