递归

自顶向下

//先替换顶层节点，再替换底层节点
var invertTree = function(root) {
    if(root === null) return null;
    //替换左右结点
    var tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    if(root.left){
        invertTree(root.left);
    }
    if(root.right){
        invertTree(root.right);
    }
    return root;
};

自底向上

//先替换底层节点，再替换顶层节点
var invertTree = function(root) {
    //定义递归返回的条件
    if(!root)   return null;
    //先应用递归找到最底层的左右子树
    let left = invertTree(root.left);
    let right = invertTree(root.right);
    //别离替换左右子树
    root.right = left;
    root.left = right;
    return root;
}

迭代

思路：保护一个数组，这个数组外面寄存的是没有替换过左右子树的节点

//思路：保护一个数组，这个数组外面寄存的是没有替换过左右子树的节点
//自顶向下
var invertTree = function(root) {
    if(!root)   return null;
    //这个数组一开始寄存的只有根结点
    var arr = [root];
    while(arr.length) {
        let current = arr.pop();
        //别离替换current节点的左右子树
        let temp = current.left;
        current.left = current.right;
        current.right = temp;

        //再判断current节点的左右子树是否存在，如果存在则放进数组
        if(current.left)    arr.push(current.left);
        if(current.right)   arr.push(current.right);
    }
    return root;
}