聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 799|回复: 10
收起左侧

[树/链表/图] 不用recursion遍历Binary Tree

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

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

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

x
不用recursion遍历Binary Tree可以实现吗?求问怎么做,实在想不出来啊
love1point 发表于 2015-6-15 08:40:06 | 显示全部楼层
  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. }
复制代码

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

全球28万学生4.7分推荐
 楼主| billyli8866 发表于 2015-6-15 08:12:34 | 显示全部楼层
LintCode里面最新的题Invert Binary Tree,一行小字说此题用递归很容易做,问怎么不用递归做
回复 支持 反对

使用道具 举报

 楼主| billyli8866 发表于 2015-6-15 08:14:06 | 显示全部楼层
LintCode里面最新的题Invert Binary Tree,一行小字说此题用递归很容易做,问怎么不用递归做
回复 支持 反对

使用道具 举报

yangzeyao 发表于 2015-6-15 08:40:38 | 显示全部楼层
BFS
  1. class Solution {
  2. public:
  3.     TreeNode* invertTree(TreeNode* root) {
  4.         TreeNode* res = root;
  5.         queue<TreeNode*> q;
  6.         if (root==NULL) {return res;}
  7.         q.push(root);
  8.         while (!q.empty()) {
  9.             TreeNode* node = q.front();
  10.             q.pop();
  11.             swap(node->left,node->right);
  12.             if (node->left) q.push(node->left);
  13.             if (node->right) q.push(node->right);
  14.         }
  15.         return res;
  16.     }
  17. };
复制代码
回复 支持 反对

使用道具 举报

yangzeyao 发表于 2015-6-15 08:40:58 | 显示全部楼层
DFS
  1. class Solution {
  2. public:
  3.     TreeNode* invertTree(TreeNode* root) {
  4.         TreeNode* res = root;
  5.         stack<TreeNode*> st;
  6.         TreeNode* node = root;
  7.         while (node || !st.empty()) {
  8.             if (node) {
  9.                 swap(node->left,node->right);
  10.                 if (node->right) { st.push(node->right);}
  11.                 node = node->left;
  12.             } else {
  13.                 node =st.top();
  14.                 st.pop();
  15.             }
  16.         }
  17.         return res;
  18.     }
  19. };
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

yangzeyao 发表于 2015-6-15 08:41:39 | 显示全部楼层
BFS
  1. class Solution {
  2. public:
  3.     TreeNode* invertTree(TreeNode* root) {
  4.         TreeNode* res = root;
  5.         queue<TreeNode*> q;
  6.         if (root==NULL) {return res;}
  7.         q.push(root);
  8.         while (!q.empty()) {
  9.             TreeNode* node = q.front();
  10.             q.pop();
  11.             swap(node->left,node->right);
  12.             if (node->left) q.push(node->left);
  13.             if (node->right) q.push(node->right);
  14.         }
  15.         return res;
  16.     }
  17. };
复制代码
回复 支持 反对

使用道具 举报

yangzeyao 发表于 2015-6-15 08:42:17 | 显示全部楼层
BFS

  1. class Solution {
  2. public:
  3.     TreeNode* invertTree(TreeNode* root) {
  4.         TreeNode* res = root;
  5.         queue<TreeNode*> q;
  6.         if (root==NULL) {return res;}
  7.         q.push(root);
  8.         while (!q.empty()) {
  9.             TreeNode* node = q.front();
  10.             q.pop();
  11.             swap(node->left,node->right);
  12.             if (node->left) q.push(node->left);
  13.             if (node->right) q.push(node->right);
  14.         }
  15.         return res;
  16.     }
  17. };
复制代码
回复 支持 反对

使用道具 举报

enirinth 发表于 2015-6-15 12:00:45 | 显示全部楼层
本帖最后由 enirinth 于 2015-6-15 14:04 编辑

在一般树中:
DFS = pre order traversal; 实现: 1. stack / 2. recursion
        = post order traversal;  实现:  3. recursion        
BFS = level order traversal ; 实现: 4. queue(无法recursion)
在二叉树中:
In order traversal 实现:5. recursion

在具体的invert tree这个场景下,把visit()定义成swap两个children就行了

queue和stack的操作流程几乎一样,都是:
visit root - (while has children): push/enqueue 所有children - pop/dequeue - visit it - push/enqueue all its children - ...  (用stack的话这是pre order, 用queue是level order)

所以理论上至少有5种办法:
比较简洁的,也是这题的“标准”解法,是方法2,3,5;三者的唯一区别就是visit()的位置在两个recursive call on subtree之后/之前/之中;虽然遍历路径区别很大;但是代码写起来区别很小,可以视作一种方法。
(非recursion楼上各位都已经给出来代码了)

————————————————————————
Update1:
post order traversal也可以用stack实现(这应该算方法6了),只不过有点复杂:

1.1 Create an empty stack2.1 Do following while root is not NULL   
  a) Push root's right child and then root to stack.   
  b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.   
  a) If the popped item has a right child and the right child is at top of stack, then remove the right child from stack,push the root back and set root as root's right child.   
  b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.
Copied from http://www.geeksforgeeks.org/ite ... versal-using-stack/
跟着操作了一遍发现确实是post order, 但还没想明白原理。。。
————————————————————————
update2:
自己又想了一个简单版本stack实现post order traversal;pesudo code如下:
node = root;
stack = empty;
While (stack != empty) {
        if (node != null) {
                push(node);
                node = node.firstChild;
        }
        else {
                top = pop();
                visit(top);
                node = top.nextSibling;
        }
}



回复 支持 反对

使用道具 举报

2006reload 发表于 2015-6-15 17:17:06 | 显示全部楼层
recursion 就是stack你能明白当前状态 把状态push 最后pop 出来就是一样了
回复 支持 反对

使用道具 举报

iker01 发表于 2015-6-15 21:15:46 | 显示全部楼层
三种traversal还可以使用Morris Traversal的方法,不适用额外空间。有些公司会考到。
http://www.cnblogs.com/AnnieKim/ ... orristraversal.html
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-22 07:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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