题解 | #二叉树的中序遍历#

简单递归

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    vector<int> inorderTraversal(TreeNode* root) {
      std::vector<int> res;
      inorder(root, res);
      return res;
    }
  private:
    void inorder(TreeNode *root, std::vector<int> &res) {
      if (root == nullptr) {
        return ;
      }
      inorder(root->left, res);
      res.push_back(root->val);
      inorder(root->right, res);
    }
};

迭代：稍微有点复杂
需要好好消化

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
      std::vector<int> res;
      std::stack<TreeNode *> stack_;
      
      while (root || !stack_.empty()) {
        while (root) {
          stack_.push(root);
          root = root->left;
        }
        TreeNode *tmp = stack_.top();
        stack_.pop();
        res.push_back(tmp->val);
        root = tmp->right;
      }
      
      return res;
    }
};