不用recursion遍历Binary Tree

不用recursion遍历Binary Tree可以实现吗？求问怎么做，实在想不出来啊

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. }

复制代码

LintCode里面最新的题Invert Binary Tree，一行小字说此题用递归很容易做，问怎么不用递归做

LintCode里面最新的题Invert Binary Tree，一行小字说此题用递归很容易做，问怎么不用递归做

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. };

复制代码

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. };

复制代码

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. };

复制代码

BFS

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

复制代码

在一般树中：
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;
        }
}

recursion 就是stack你能明白当前状态 把状态push 最后pop 出来就是一样了