0094.md

• 递归形式，时间复杂度 O(n)（T(n) = T(n / 2) + 1），空间复杂度 O(h)（h 为树高，平均为 log n，最差为 n）

class Solution {
 public:
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    dfs(root, res);
    return res;
  }

  void dfs(TreeNode* root, vector<int>& res) {
    if (!root) {
      return;
    }
    dfs(root->left, res);
    res.emplace_back(root->val);
    dfs(root->right, res);
  }
};

• 非递归形式，时间复杂度O(n)，空间复杂度O(n)

class Solution {
 public:
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* t = root;
    while (t || !empty(s)) {
      while (t) {
        s.emplace(t);
        t = t->left;
      }
      t = s.top();
      s.pop();
      res.emplace_back(t->val);
      t = t->right;
    }
    return res;
  }
};

• Morris遍历，线索二叉树的思路，利用叶子节点的右节点（原本为空）存储下一个要遍历的节点

设置一个 cur 指针，初始化为根节点

如果 cur 无左节点，添加 cur 到输出，访问右节点，cur = cur->right

如果 cur 有左节点
1. 找到左子树的最右节点 p
2. 令左子树最右节点的下一节点（原本为空）指向 cur，即p->right = cur
3. 访问左节点，cur = cur->left
如果 2. 中已经设置过 p->right，则说明左子树已遍历完成，添加 cur 到输出
重新将 p->right 置空，接着访问右节点，cur = cur->right

    4
   / \
  2   6
 / \ / \
1  3 5  7
// 1->right 为 2
// 3->right 为 4
// 5->right 为 6

cur为 4，左子树的最右节点为 3，令 3->right 为 4
cur为 2，左子树的最右节点为 1，令 1->right 为 2
cur为 1，无左子树，输出 1，访问右节点 2（1->right 为2 ）
cur为 2，左子树的最右节点为本身（1->right 为 2），说明左子树已遍历完毕
=>重置左子树的最右节点为空（1->right 为空），输出 2，访问 2->right

cur为 3，无左子树，输出 3，访问 3->right（为4）
cur为 4，左子树最右节点为 本身（3->right为4），输出 4，重置 3->right 为空，访问 4->right
cur为 6，左子树最右节点为 5，令 5->right 为 6
cur为 5，无左子树，输出 5，访问 5->right（为6）
cur为 6，左子树为右节点为本身（5->right 为 6），输出 6，重置 5->right 为空，访问 6->right
cur为 7，无左子树，输出 7，访问右节点，cur为 7->right
cur为空，访问结束

• 时间复杂度 O(n)（每条边最多经过两次），空间复杂度 O(1)，Morris 遍历实现如下

class Solution {
 public:
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    while (root) {
      if (!root->left) {  // 无左子树则右移
        res.emplace_back(root->val);
        root = root->right;
      } else {  // 有左子树，先获取左子树的最右节点
        TreeNode* t = getLeftMostRight(root);
        if (t->right == root) {  // 最右节点的下一节点如果指向根节点，则断开链接
          t->right = nullptr;
          res.emplace_back(root->val);
          root = root->right;
        } else {  // 最右节点的下一节点未指向根节点
          // 把上一个 res.emplace_back(root->val) 移到这里则为前序遍历
          t->right = root;
          root = root->left;
        }
      }
    }
    return res;
  }

  TreeNode* getLeftMostRight(TreeNode* root) {
    TreeNode* t = root->left;
    while (t && t->right && t->right != root) {
      t = t->right;
    }
    return t;
  }
};