226. Invert Binary Tree

题干简述：

翻转一个二叉树。

翻转：交换二叉树的左右子节点位置，根节点不会动。

解题思路

看完题目后，我心想，不愧是简单难度的题目，着实简单。利用递归，交换节点左右子树不就可以了。自信的我直接写出了如下所示的代码：

var invertTree = function(root) {
    const revert = (node) => {
        if (!node) return null;
        node.left = revert(node.right);
        node.right = revert(node.left);
        return node;
    }
    revert(root);
    return root;
};

Run code 之后，却发现出现了一个奇怪的结果：

image-20210710213607799

简单分析一下出现的结果，我们会发现根节点 4 的左右子节点交换后，左子节点变成了之前的右子节点 7，但是现在的右子节点依旧是 7，这是为什么呢？难道是逻辑没有执行吗？显然，并不是这样。让我们重新来看一下一个二叉树通过怎样的数据结构展示的。在这里，是通过链表的形式，每个节点的左右子树，都是通过存储一个指针指向其在内存中的位置来得到的。我们在直接通过 node.left = revert(node.right); 设置了左子节点后，此时存储的指针已经发生了变化，指向的是之前的右子节点；所以在后面的 node.right = revert(node.left); 执行时，这里的 node.left 的值是和 node.right 相等的，故而还是 7。

image-20210710215047483

为了解决这个问题，我们需要在交换前对节点先做一次存储，这也是涉及到链表的题目中的常见操作。

题解

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    const revert = (node) => {
        if (!node) return null;
        const temp = node.left;
        node.left = revert(node.right);
        node.right = revert(temp);
        return node;
    }
    revert(root);
    return root;
};

思考

这道题很简单，但是仔细想想的话，其实还是蛮有嚼头的。上面我的解法非常简单，其本质就是二叉树的前序遍历，也就是先处理根节点，再通过递归去处理根节点的两个子节点；换一种思路，先递归处理根节点的两个子节点，再处理根节点，一样的效果，不过这个时候就变成了后序遍历了。为什么这里不用中序遍历呢？原因在于如果使用中序遍历，先处理左子树，再处理根节点，到这里都是ok的，但是在处理完根节点后，此时原本的右子树会被替换为先前的左子树的值，此时再递归处理右子树，相当于还是在处理之前的左子树，会导致丢失原本的右子树数据。

除了通过递归，也就是 DFS 深度优先的算法外，我们还可以通过 Queue 队列 BFS 广度优先遍历的方式实现。实现思路简单来说，就是通过一个数组维护一个根节点的队列，每当有根节点出列时，交换它的左右子树，并将左右子树的根节点入列；重复这个操作，直到队列为空时即完成了翻转。

这里是 BFS 的实现，大家可以参考一下。

var invertTree = function(root) {
  if (!root) return null;
  
  const queue = [root]; // 通过数组维护队列
  
  // while 循环
  while(queue.length) {
    const temp = queue.shift(); // 出列
    [temp.left, temp.right] = [temp.right, temp.left]; // 交换左右子节点位置
    if (temp.left) queue.push(temp.left);
    if (temp.right) queue.push(temp.right); // 交换后的左右子节点入列
  }
  return root;
};

Q.E.D.

Take it easy