LeetCode:Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

递归的方法这里就不多说，下面主要提供两个非递归算法：1、使用栈的非递归中序遍历；2、不使用栈的非递归中序遍历（Morris 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> inorderTraversal(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*> mystack;
18         TreeNode *p = root;
19         while(p || mystack.empty() == false)
20         {
21             while(p)
22             {
23                 mystack.push(p);
24                 p = p->left;
25             }
26             if(mystack.empty() == false)
27             {
28                 p = mystack.top();
29                 res.push_back(p->val);
30                 mystack.pop();
31                 p = p->right;
32             }
33         }
34         return res;
35     }
36 };

算法2：关于Morris Traversal算法，他是基于线索二叉树，它利用二叉树节点中闲置的右指针指向该节点在中序序列中的后缀节点。可以参考here 和 here。该算法的空间复杂度为O(1)

文中给出算法步骤如下：

1. Initialize current as root 
2. While current is not NULL
   If current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as right child of the rightmost node in current's left subtree
      b) Go to this left child, i.e., current = current->left

总结一下就是：本文地址

重复以下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> inorderTraversal(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 = NULL, *pre = NULL;
16           vector<int> res;
17           current = root;
18           while(current != NULL)
19           {                 
20                 if(current->left == NULL)
21                 {
22                       res.push_back(current->val);
23                       current = current->right;      
24                 }    
25                 else
26                 {
27                       /* Find the inorder predecessor of current */
28                       pre = current->left;
29                       while(pre->right != NULL && pre->right != current)
30                         pre = pre->right;
31                         
32                       if(pre->right == NULL)
33                       {     /* Make current as right child of its inorder predecessor */
34                             pre->right = current;
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                             res.push_back(current->val);
43                             current = current->right;      
44                       } 
45                 }
46           } 
47           return res;
48     }
49 };