翻转二叉树

1. 举例：
   翻转一棵二叉树。

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

2. 解题思路：

2.1递归版本

首先思考：
（1）分解问题后的子问题是什么？也就是重复的那部分是啥？
（2）什么时候终止重复，结束条件是啥？

从root开始，将root.left和root.right交换。
从root.left开始，将root.left.left和root.left.right交换。
从root.right开始，将root.right.left和root.right.right交换。

由上分析我们可知，重复的部分是交换X元素的左右孩子。

temp = X.left;
X.left = X.right;
X.right = temp;

终止条件是当元素X为null的时候。所以当X=null的时候终止递归。

function TreeNode(x) {
  this.left = null;
  this.right = null;
  this.value = x;
}

function invertTree(root) {
  //  终止条件
  if(root === null) return;
  //  重复操作
  let temp = root.left;
  root.left = root.right;
  root.right = temp;
  //  分别对左右子节点进行同样的操作
  invertTree(root.left);
  invertTree(root.right);
  return root;
}

2.2 非递归版本
可以参考二叉树的层次遍历。

function TreeNode(x) {
  this.left = null;
  this.right = null;
  this.value = x;
}

function invertTree(root) {
  if(root === null) return;
  //  创建一个队列来辅助
  let queue = [];
  queue.push(root);
  
  while(queue.length !== 0) {
    //  弹出队列头的元素，交换它的左右孩子
    let cur = queue.shift();
    if(cur !== null) {
       let temp = cur.left;
       cur.left = cur.right;
       cur.right = temp;

       queue.push(root.left);  //  左孩子入队
       queue.push(root.right);  // 右孩子入队
    }
  }
}