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

方法一：递归

二叉树的中序遍历顺序：左节点->根节点->右节点。先递归遍历左子树，再保存根节点的值，再递归遍历右子树。

时间复杂度：o(n)。需要遍历二叉树的所有节点，需要o(n)。

空间复杂度：o(n)。需要开辟空间保存中序遍历的节点值。

class Solution {
  public:
    void in_search(TreeNode* root, vector<int>& in_tree) {
	  	//节点为空时返回
        if (root == nullptr)
            return;

        //中序遍历先遍历左节点
        in_search(root->left, in_tree);
        //遍历根节点
        in_tree.push_back(root->val);
        //遍历右节点
        in_search(root->right, in_tree);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> in_tree;
        in_search(root, in_tree);
        return in_tree;
    }
};

方法二：栈（非递归）

跟前序遍历类似，利用栈来替代递归求解。

具体做法：

• step 1：优先判断树是否为空，空树不遍历。
• step 2：准备辅助栈，当二叉树节点为空了且栈中没有节点了，我们就停止访问。
• step 3：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
• step 4：到达最左后，可以开始访问，如果它还有右节点，则将右边也加入栈中，之后右子树的访问也是优先到最左。

时间复杂度：o(n)。

空间复杂度：o(n)。

class Solution {
  public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> in;
        //特殊情况处理
        if (root == nullptr)
            return in;

        stack<TreeNode*> temp;

        while (!temp.empty() || root != nullptr) {
            //每次找到最左边的结点
            while (root != nullptr) {
                temp.push(root);
                root = root->left;
            }
            TreeNode* node = temp.top();
            in.push_back(node->val);
            temp.pop();
            //进入右节点
            root = node->right;
        }

        return in;
    }
};