翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
思路：
使用递归，交换当前节点左右子树，然后分别向两个子树递归
性能分析：
遍历整棵树，时间复杂度O(N)
每层记录一个root值，空间复杂度O(logN)
具体代码：
/**
* 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;
}
//交换当前节点左右子树
TreeNode t = root.left;
root.left = root.right;
root.right = t;
//向左子树递归
invertTree(root.left);
//向右子树递归
invertTree(root.right);
return root;
}
}
借鉴代码
参考资料《Leetcode 226: Invert Binary Tree(二叉树反转 递归、非递归实现)》
非常棒的写法，用短短几行，实现了两个功能：1、交换左右子树；2、向左右子树递归
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){ //空节点直接返回
return null;
}
TreeNode t = root.left;
root.left = invertTree(root.right);
root.right = invertTree(t);
return root;
}
}
