一亩三分地论坛

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

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

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

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

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

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

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

使用道具 举报

 楼主| 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
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 04:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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