Morris Traversal遍历二叉树

1. 什么是Morris Traversal

这是一个时间复杂度与我们以前遍历二叉树一样，而空间复杂度为常数的算法。

这里引入一个空闲指针的概念
因为我们不能使用栈结构，所以我们需要一个指针来使下层节点可以返回上层，那么就是下面的cur。空闲指针由root节点的左子树的最右子树的右指针指向root节点。（如下面的cur->right = root;）

下面内容大多来自 Annie Kim 以及蜗牛

1. 前序遍历二叉树

1. 判断当前节点的左子树是否为空，如果为空则输出当前节点并将cur指向当前节点的右子树
2. 如果左子树不为空，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. 中序遍历二叉树

与前序遍历几乎一模一样！只是输出数据位置的不同。