My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null)
return root;
revertTree(root);
return root;
}
private void revertTree(TreeNode root) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
if (root.left != null)
revertTree(root.left);
if (root.right != null)
revertTree(root.right);
}
}
今天做了三道简单题。。。
这道题木也是最简单的递归思想。
只不过据说这道题木某个大牛面试谷歌的时候没做出来，然后说了如下这么一句话。
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
哈哈。看来技术是和算法数据结构相关的，但也不需要像刷题这样，对他们那么了解，变态的了解。
只不过这么一道题目，其实并不是很难。大牛怎么会做不出来。
还有，现实中，要用到高端算法的情况，好像少之又少。
**
总结： recursive
**
Anyway, Good luck, Richardo!
recursion
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
iteration
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
TreeNode left = node.left;
node.left = node.right;
node.right = left;
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
return root;
}
}
iteration 的方法要注意下。这也算是一种新的level order
进去之后不用再循环一次。
再循环一次也差不多。
Anyway, Good luck, Richardo! -- 08/28/2016
