[Leetcode]226. Invert Binary Tree

Invert a binary tree.

     4
   /   
  2     7
 /    / 
1   3 6   9

to

     4
   /   
  7     2
 /    / 
9   6 3   1

思路：这道题考的是树的遍历，先序和后序遍历都行，唯独中序遍历不行。eg:如上图，如果用中序遍历
　　　递归返回到 2 这个节点的时候，2 的左右已经互换，即 2.left.val = 3,2.right.val =1
　　　然后返回到4这个节点，接着 2，7互换。继续递归 4 的右边，此时 7 变为左节点，然而 6，7
　　　还未互换，而递归右边时，又把2 的左右互换了回来。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root==null)
            return null;
        else {
            TreeNode tmp = root.left;                        //先序，先交换左右，再递归
            root.left = root.right;
            root.right = tmp;
            root.left = invertTree(root.left);
            root.right = invertTree(root.right);
        }
        return root;
    }
}