翻转一棵二叉树。
示例：
输入：
1
2
3
4
5
| 4
/ \
2 7
/ \ / \
1 3 6 9
|
输出：
1
2
3
4
5
| 4
/ \
7 2
/ \ / \
9 6 3 1
|
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
递归求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root==null||(root.left==null&&root.right==null)){
return root;
}
TreeNode tmp=root.left;
root.left=root.right;
root.right=tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
|