94. 二叉树的中序遍历

class Solution {
public:
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> Result;
    stack<TreeNode *> Stack;

    while (root || !Stack.empty()) {
      while (root) {
        Stack.push(root);
        root = root->left;
      }
      root = Stack.top();
      Stack.pop();
      Result.push_back(root->val);
      root = root->right;
    }

    return Result;
  }
};

class Solution {
public:
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> Result;
    stack<TreeNode *> S;

    // These two while conditions correspond to:
    // if (!root)
    //   return;
    // And also the IMPLICIT return statement at the end of the function.
    while (!S.empty() || root) {
      while (root) {
        // Traverse(root->left);
        S.push(root);
        root = root->left;
      }
      // Visit(root); Note that this is basically a BACKTRACK.
      root = S.top();
      S.pop();
      Result.push_back(root->val);
      // Traverse(root->right);
      root = root->right;
    }

    return Result;
  }
};

class Solution {
public:
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> Ret;
    stack<TreeNode *> S;
    // The predicative looks like this because the root IS NOT PRESUMABLY NON-
    // NULL, thus we need to perform a double-check: one for the root, another
    // for the stack.
    while (root != nullptr || !S.empty()) {
      // The fixed point in every tree traversal algorithm is always `!root`,
      // instead of `!root->left` or `!root->right`.
      while (root != nullptr) {
        S.push(root);
        root = root->left;
      }
	  // else {
      // After the while loop above, root will always be nullptr; so we shall
      // get the root IN THE PREVIOUS LAYER through the stack.
      root = S.top();
      Ret.emplace_back(root->val);
      S.pop();
      // Now we're safe to traverse the right part.
      root = root->right;
      // }
    }
    return Ret;
  }
};