一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 791|回复: 13
收起左侧

[算法题] Invert binary tree

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-6-12 21:43:03 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Invert binary tree:

这两天相信大家看到了关于google不招聘某H大神,我们暂时不去讨论这件事,反正感谢这件事让我们多了一道leetcode题哈。

一看到binary tree, 非常容易用递归可以解决
  1. public class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         if(root == null)
  4.         {
  5.             return null;
  6.         }
  7.         TreeNode left = root.left;
  8.         TreeNode right = root.right;
  9.         root.left = invertTree(right);
  10.         root.right = invertTree(left);
  11.         return root;
  12. }
  13. }
复制代码
nunuh89 发表于 2015-6-13 03:03:44 | 显示全部楼层
认识真人  觉得还是比较 前端  比较有经验  算法什么的 不怎么熟
回复 支持 1 反对 0

使用道具 举报

 楼主| love1point 发表于 2015-6-12 22:02:36 | 显示全部楼层
这种树的题目用迭代更好理解哈。
  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. *     int val;
  5. *     TreeNode left;
  6. *     TreeNode right;
  7. *     TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. public class Solution {
  11.     public TreeNode invertTree(TreeNode root) {
  12.         if(root == null)
  13.         {
  14.             return null;
  15.         }
  16.         LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
  17.         queue.offer(root);
  18.         
  19.         while(!queue.isEmpty())
  20.         {
  21.             TreeNode node = queue.poll();
  22.             TreeNode left = node.left;
  23.             node.left = node.right;
  24.             node.right = left;
  25.             
  26.             if(node.left != null)
  27.             {
  28.                 queue.offer(node.left);
  29.             }
  30.             
  31.             if(node.right != null)
  32.             {
  33.                 queue.offer(node.right);
  34.             }
  35.         }
  36.         return root;
  37. }
  38. }
复制代码
回复 支持 反对

使用道具 举报

bitcpf 发表于 2015-6-12 22:14:39 | 显示全部楼层
Leetcode  已经与时俱进的加了这个题。。。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-12 22:15:37 | 显示全部楼层
bitcpf 发表于 2015-6-12 22:14
Leetcode  已经与时俱进的加了这个题。。。

是的,他们速度很快,够fashion
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-13 00:01:51 | 显示全部楼层
love1point 发表于 2015-6-12 22:02
这种树的题目用迭代更好理解哈。

我来加一个迭代DFS版本的:
  1.    
  2. TreeNode* invertTree(TreeNode* root) {
  3.         if (!root) return root;
  4.         stack<TreeNode*> st;
  5.         TreeNode* cur = root;
  6.         while(cur || !st.empty()) {
  7.             if (cur) {
  8.                 swap(cur->left, cur->right);
  9.                 if (cur->right) st.push(cur->right);
  10.                 cur = cur->left;
  11.             }
  12.             else {
  13.                 cur = st.top();
  14.                 st.pop();
  15.             }
  16.         }
  17.         return root;
  18.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-13 00:16:27 | 显示全部楼层
stellari 发表于 2015-6-13 00:01
我来加一个迭代DFS版本的:

虽然我现在对C++不熟,但还是多谢你的添加哈
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-13 09:08:18 | 显示全部楼层
nunuh89 发表于 2015-6-13 03:03
认识真人  觉得还是比较 前端  比较有经验  算法什么的 不怎么熟

认识牛人的人也是牛人哈。他前端的,咋不面前端的东西啊
回复 支持 反对

使用道具 举报

nunuh89 发表于 2015-6-13 10:16:09 | 显示全部楼层
love1point 发表于 2015-6-12 17:08
认识牛人的人也是牛人哈。他前端的,咋不面前端的东西啊

不知道 可能google都会问吧

他以前应该做过backend  不过最近一直做frontend contract

其实 就是没有刷题 =。=||| 所以说 同学还是好好刷题把
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-13 10:39:51 | 显示全部楼层
再来一个:
  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. *     int val;
  5. *     TreeNode left;
  6. *     TreeNode right;
  7. *     TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. public class Solution {
  11.     public TreeNode invertTree(TreeNode root) {
  12.         if(root == null)
  13.         {
  14.             return null;
  15.         }
  16.         TreeNode temp = root.left;
  17.         root.left = root.right;
  18.         root.right = temp;
  19.         invertTree(root.left);
  20.         invertTree(root.right);
  21.         return root;
  22. }
  23. }
复制代码
回复 支持 反对

使用道具 举报

cqx83 发表于 2015-6-13 13:40:24 | 显示全部楼层

能解释下这个版本和第一个版本有什么区别么
回复 支持 反对

使用道具 举报

EroicaCMCS 发表于 2015-6-13 19:30:00 | 显示全部楼层
这件事的影响力在于LeetCode上发布了不到一天的题竟然已经有上万次提交了!

来一个py版本的:

  1. class Solution:
  2.     # @param {TreeNode} root
  3.     # @return {TreeNode}
  4.     def invertTree(self, root):
  5.         if not root:
  6.             return

  7.         root.left, root.right = root.right, root.left
  8.         self.invertTree(root.left)
  9.         self.invertTree(root.right)
  10.         return root
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-13 19:48:47 | 显示全部楼层
EroicaCMCS 发表于 2015-6-13 19:30
这件事的影响力在于LeetCode上发布了不到一天的题竟然已经有上万次提交了!

来一个py版本的:

我有留意过新题出来,一天实际至少会有几千都提交量,还是现在刷题的人太多了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 08:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表