Invert a binary tree.
4 / \ 2 7 / \ / \ 1 3 6 9
to
4 / \ 7 2 / \ / \ 9 6 3 1
这道题呢=。=看着题目简介挺有意思的。哈哈哈。~说实话我真的很讨厌whiteboard上直接来代码。
因为要翻转的BTS已经给出来了，灰常短小的一个啊~所以按照自己的喜好whatever交换就好了。
因为这里BTS已经给出来了所以可以偷懒直接交换（毕竟这么短小），这个比较取巧。代码如下。
public class Solution {
public TreeNode invertTree(TreeNode root) {
//invert directly
TreeNode left=root.left;
TreeNode right=root.right;
root.left=invertTree(right);
root.right=invertTree(left);
return root;
//special case
if(root==null){
return null;
}
}
}
然后呢贴一个常规思维来的，这是program creek上的。我大概写了一下，懒得run了。就贴一个确定accepted的答案好了。
这个就是踏踏实实一个一个看的。
public TreeNode invertTree(TreeNode root) {
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
if(root!=null){
queue.add(root);
}
while(!queue.isEmpty()){
TreeNode p = queue.poll();
if(p.left!=null)
queue.add(p.left);
if(p.right!=null)
queue.add(p.right);
TreeNode temp = p.left;
p.left = p.right;
p.right = temp;
}
return root;
}