LeetCode:Binary Tree Postorder Traversal

题目：非递归实现二叉树的后序遍历。题目链接

算法1：非递归使用栈。首先把根节点压栈，然后循环如下操作：用一个变量来记录上次访问的节点，如果当前栈顶元素左右儿子都为空或者上次访问的节点非空且等于栈顶节点的左儿子或右儿子，则直接访问；否则把栈顶元素的右节点和左节点依次压栈。代码如下：

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> postorderTraversal(TreeNode *root) {
13         // IMPORTANT: Please reset any member data you declared, as
14         // the same Solution instance will be reused for each test case.
15         vector<int>res;
16         if(root == NULL)return res;
17         stack<TreeNode *> nstack;
18         nstack.push(root);
19         TreeNode *pre = NULL;//指向上次访问的节点
20         while(nstack.empty() == false)
21         {
22             TreeNode *p = nstack.top();
23             if((p->left == NULL && p->right == NULL) || 
24                 (pre != NULL && (pre == p->left || pre == p->right)))
25             {
26                 res.push_back(p->val);
27                 nstack.pop();
28                 pre = p;
29             }
30             else
31             {
32                 if(p->right)
33                     nstack.push(p->right);
34                 if(p->left)
35                     nstack.push(p->left);
36             }
37         }
38         return res;
39     }
40 };

算法2：非递归不使用栈（Morris Traversal算法），只要在Morris Traversal中序遍历的算法基础上要做较大改动，它和中序morris遍历有所不同，在发现当前结点左子树为空时，不访问此结点(后序遍历需要保证访问完右子树后才能访问根结点)，直接访问右子树。

第二次遍历到某个结点时，将该结点左子树的最右路径（右指针所在的路径）反序输出即可。步骤如下，代码中红色部分是修改的：

建立一个临时节点dump，令其左孩子是root，右孩子为空

当前节点设置为临时节点dump。

重复以下1、2直到当前节点为空。

1. 如果当前节点的左孩子为空，则将其右孩子作为当前节点。

2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。

a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。

b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。倒序输出从当前节点的左孩子到前驱节点这条路径上的所有节点。当前节点更新为当前节点的右孩子。

注意：倒序输出路径上的节点时，由于题目O(1)的空间要求不能使用栈，因此要先翻转路径，输出后，再恢复

比如下面的树：

当第二次访问到6时，输出8,；第二次访问2时，输出9、6、4；第二次访问1时输出7、5、2，第二次访问dump节点时输出1、3

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<int> postorderTraversal(TreeNode *root) {
13         // IMPORTANT: Please reset any member data you declared, as
14         // the same Solution instance will be reused for each test case.
15         vector<int>res;
16         if(root == NULL)return res;
17         TreeNode dump(0);
18         dump.left = root;
19         TreeNode *cur = &dump, *prev = NULL;
20         while (cur)
21         {
22             if (cur->left == NULL)
23             {
24                 cur = cur->right;
25             }
26             else
27             {
28                 prev = cur->left;
29                 while (prev->right != NULL && prev->right != cur)
30                     prev = prev->right;
31     
32                 if (prev->right == NULL)
33                 {
34                     prev->right = cur;
35                     cur = cur->left;
36                 }
37                 else
38                 {
39                     printReverse(cur->left, prev, res);  // visit node
40                     prev->right = NULL;
41                     cur = cur->right;
42                 }
43             }
44         }
45         return res;
46     }
47     void reverse(TreeNode *from, TreeNode *to) // reverse the tree nodes 'from' -> 'to'.
48     {
49         if (from == to)
50             return;
51         TreeNode *x = from, *y = from->right, *z;
52         do
53         {
54             z = y->right;
55             y->right = x;
56             x = y;
57             y = z;
58         }while(x != to);
59     }
60 
61     void printReverse(TreeNode* from, TreeNode *to, vector<int> &res) // print the reversed tree nodes 'from' -> 'to'.
62     {
63         reverse(from, to);
64         
65         TreeNode *p = to;
66         while(true)
67         {
68             res.push_back(p->val);
69             if (p == from)
70                 break;
71             p = p->right;
72         }
73         
74         reverse(to, from);
75     }
76 
77 };