LeetCode JS翻转二叉树：操作队列节点为何最终返回root？

题面与参考代码 #

翻转二叉树的核心操作逻辑为：

• 创建新的TreeNode节点
• 将root的left子节点赋值到right位置
• 将root的right子节点赋值到left位置

对应的广度优先遍历实现代码如下：

function invertTree(root) {
  const queue = [root];
  while (queue.length) {
    const n = queue.pop();
    if (n != null) {
      [n.left, n.right] = [n.right, n.left];
      queue.push(n.left, n.right);
    }
  }
  return root;
};

问题解答 #

为什么操作queue内的元素没有直接修改root变量，最终还要返回root？ #

JavaScript里所有对象类型（本题的TreeNode实例就属于对象）在赋值、传参时传递的都是内存引用地址，不是完整的节点拷贝。代码里从queue中取出节点n后修改它的left、right属性，本质是直接操作对应内存地址上的真实节点数据，整棵树从根节点开始的结构是被原地修改的。
整个执行过程中从来没有替换过根节点本身，变量root始终指向最初的根节点内存地址，只是根节点和所有子节点的左右子节点指针被调换了。题目要求函数返回翻转后二叉树的根节点，直接返回root即可。

为什么queue中存储的是节点引用而非拷贝？ #

这个行为和数组的创建方式完全无关，不管你用字面量[]还是new Array()创建数组，只要存入的是对象类型，默认存的都是引用地址。
JS中只有原始类型（数字、字符串、布尔、null、undefined等）在赋值时会直接拷贝值，所有对象（包括自定义类的实例、数组、普通对象等）都不会自动做拷贝。如果真的需要存入节点的备份，必须手动写深拷贝逻辑，递归复制每个节点的val、left、right属性，引擎不会自动做这个操作。
你可以用几行简单代码验证这个逻辑：

const demoNode = { val: 1, left: null, right: null };
const queue = new Array(demoNode);
queue[0].val = 2;
console.log(demoNode.val); // 输出2，二者指向同一个对象

为什么没有直接修改root变量，root对应的树结构却发生了变化？ #

代码里从来没有给root变量本身重新赋值（即没有出现过root = xxx的写法），修改的只是root指向的内存地址中存储的对象属性。你可以把变量理解成写着内存地址的门牌号，整个过程你从来没换过门牌号，只是开门进房把房间里的左右家具调换了位置，门牌号对应的房子还是原来的，自然root指向的就是翻转完成的树。

内容的提问来源于stack exchange，提问作者Yujin Dong