1. 什么是Morris Traversal
这是一个时间复杂度与我们以前遍历二叉树一样，而空间复杂度为常数的算法。
这里引入一个空闲指针的概念
因为我们不能使用栈结构，所以我们需要一个指针来使下层节点可以返回上层，那么就是下面的cur。空闲指针由root节点的左子树的最右子树的右指针指向root节点。（如下面的cur->right = root;）
1. 前序遍历二叉树
- 判断当前节点的左子树是否为空，如果为空则输出当前节点并将cur指向当前节点的右子树
- 如果左子树不为空，cur指向当前节点的左子树
a. 如果cur指向的节点的右子树存在与当前节点相等，将cur的右子树置空，当前节点变为当前节点的右子树
b. 如果不相等，输出当前节点，cur的右子树置当前节点，当前节点置为当前节点的左子树
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
vector<int> preOrederMorrisTraversal(TreeNode *root){
vector<int> tree;
TreeNode *cur = nullptr;
while(!root)
{
if(root->left)
{
cur = root->left;
while(!cur->right&&cur->right!=root)
cur = cur->right;
if(cur->right==root)
{
cur->right = nullptr;
root = root ->right;
}
else
{
tree.push_back(root->val);
cur->right = root;
root = root->left;
}
}
else
{
tree.push_back(root->val);
root = root->right;
}
}
return tree;
}
2. 中序遍历二叉树
与前序遍历几乎一模一样！只是输出数据位置的不同。
