LeetCode:Binary Tree Preorder 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> preorderTraversal(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         while(nstack.empty() == false)
20         {
21             TreeNode *p = nstack.top();
22             res.push_back(p->val);
23             nstack.pop();
24             if(p->right)nstack.push(p->right);
25             if(p->left)nstack.push(p->left);
26         }
27         return res;
28     }
29 };

算法2：不使用栈的非递归前序遍历（Morris Traversal算法），只要在Morris Traversal中序遍历的算法基础上修改代码节点访问顺序即可，步骤如下，代码中红色部分是修改的

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

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

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

a) 输出当前节点。（相对中序遍历，输出位置改变了）。如果前驱节点的右孩子为空，将它的右孩子设置为当前节点（利用这个空的右孩子指向它的后缀）。当前节点更新为当前节点的左孩子。

b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。当前节点更新为当前节点的右孩子。

 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> preorderTraversal(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           TreeNode *current = root, *pre = NULL;
16           vector<int> res;
17           while(current != NULL)
18           {                 
19                 if(current->left == NULL)
20                 {
21                       res.push_back(current->val);
22                       current = current->right;      
23                 }    
24                 else
25                 {
26                       /* Find the inorder predecessor of current */
27                       pre = current->left;
28                       while(pre->right != NULL && pre->right != current)
29                         pre = pre->right;
30                         
31                       if(pre->right == NULL)
32                       {     /* Make current as right child of its inorder predecessor */
33                             pre->right = current;
34                             res.push_back(current->val);
35                             current = current->left;
36                       }
37                       else 
38                       {
39                             /* Revert the changes made in if part to restore the original 
40                             tree i.e., fix the right child of predecssor */   
41                             pre->right = NULL;//中序是在这里输出
42                             current = current->right;      
43                       } 
44                 }
45           } 
46           return res;
47     }
48 };