226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
翻转前：

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

翻转后：

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

参考前序遍历二叉树的实现

public TreeNode invertTree(TreeNode node) {
    // 递归的结束条件
    if (node == null) {
        // 终止时处理办法
        return null;
    }
    // 当前节点需要做的事情
    nodeNeedTodo(node);
    // 让当前节点的左子节点重复当前节点
    invertTree(node.left);
    // 让当前节点的右子节点重复当前节点
    invertTree(node.right);
    return node;
}
/**
 * 实现左子节点和右子节点对换
 */
private void nodeNeedTodo(TreeNode node) {
    TreeNode temp = node.left;
    node.left = node.right;
    node.right = temp;
}

public static void main(String[] args) {
    Integer[] arr = {4,2,7,1,3,6,9};
    TreeNode root = BinaryTreeUtil.arrToTree(arr);
    root = invertTree(root);
    BinaryTreePrintUtil.print(root);
}

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

运行结果，符合期望

参考中序遍历二叉树的实现

public TreeNode invertTree(TreeNode node) {
    // 递归的结束条件
    if (node == null) {
        // 终止时处理办法
        return null;
    }
    // 让当前节点的左子节点重复当前节点
    invertTree(node.left);
    // 当前节点需要做的事情
    nodeNeedTodo(node);
    // 让当前节点的右子节点重复当前节点
    invertTree(node.right);
    return node;
}
/**
 * 实现左子节点和右子节点对换
 */
private void nodeNeedTodo(TreeNode node) {
    TreeNode temp = node.left;
    node.left = node.right;
    node.right = temp;
}

public static void main(String[] args) {
    Integer[] arr = {4,2,7,1,3,6,9};
    TreeNode root = BinaryTreeUtil.arrToTree(arr);
    root = invertTree(root);
    BinaryTreeUtil.levelOrderPrint(root);
}

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

运行结果，不符合期望

参考后序遍历二叉树的实现

public TreeNode invertTree(TreeNode node) {
    // 递归的结束条件
    if (node == null) {
        // 终止时处理办法
        return null;
    }
    // 让当前节点的左子节点重复当前节点
    invertTree(node.left);
    // 让当前节点的右子节点重复当前节点
    invertTree(node.right);
    // 当前节点需要做的事情
    nodeNeedTodo(node);
    return node;
}
/**
 * 实现左子节点和右子节点对换
 */
private void nodeNeedTodo(TreeNode node) {
    TreeNode temp = node.left;
    node.left = node.right;
    node.right = temp;
}

public static void main(String[] args) {
    Integer[] arr = {4,2,7,1,3,6,9};
    TreeNode root = BinaryTreeUtil.arrToTree(arr);
    root = invertTree(root);
    BinaryTreeUtil.levelOrderPrint(root);
}

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

运行结果，符合期望

思考

为什么参考中序遍历二叉树的实现不符合期望而参考前序和后序遍历二叉树的实现符合期望？

前序遍历：先操作根节点，然后操作根节点的左子树，最后操作根节点的右子树
先操作根节点，把左子树和右子树对换了一下；然后操作左子树（即最初的右子树）。完成左子树的翻转；最后操作右子树（即最初的左子树），完成右子树的翻转。

后序遍历：先操作根节点的左子树，然后操作根节点的右子树，最后操作根节点
先操作左子树，完成左子树的翻转；然后操作右子树，完成右子树的翻转；最后操作根节点，对换左子树和右子树。

中序遍历：先操作根节点的左子树，然后操作根节点，最后操作根节点的右子树
先操作左子树，完成左子树的翻转；然后操作根节点，对换左子树和右子树；最后操作右子树（实际是翻转后的初始左子树），翻转右子树，实际上变成了初始的左子树
所以最终结果是仅完成了根节点的左子树和右子树对换，左子树和右子树内部并没有完成翻转

树节点对象

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(){}
    TreeNode(int val) {this.val = val;}
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}