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

题目的主要信息：

给定一颗二叉树的根节点，输出其前序遍历的结果

方法一：递归

具体做法：

什么是二叉树的中序遍历，简单来说就是“左根右”，展开来说就是对于一棵二叉树，我们优先访问它的左子树，等到左子树全部节点都访问完毕，再访问根节点，最后访问右子树。同时访问子树的时候，顺序也与访问整棵树相同。

从上述对于中序遍历的解释中，我们不难发现它存在递归的子问题，根节点的左右子树访问方式与原本的树相同，可以看成一颗树进行中序遍历，因此可以用递归处理：

终止条件： 当子问题到达叶子节点后，后一个不管左右都是空，因此遇到空节点就返回。
返回值： 每次处理完子问题后，就是将子问题访问过的元素返回，依次存入了数组中。
本级任务： 每个子问题优先访问左子树的子问题，等到左子树的结果返回后，再访问自己的根节点，然后进入右子树。

class Solution {
public:
    void inorder(vector<int> &res, TreeNode* root){
        if(root == NULL) //遇到空节点则返回
            return;
        inorder(res, root->left); //先遍历左子树
        res.push_back(root->val); //再遍历根节点
        inorder(res, root->right); //最后遍历右子树
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(res, root);  //递归中序遍历
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点数，遍历二叉树所有节点
空间复杂度： $O (n)$ ，最坏情况下二叉树化为链表，递归栈深度为 $n$

方法二：非递归

具体做法：

与前序遍历类似，我们利用栈来代替递归。如果一棵二叉树，对于每个根节点都优先访问左子树，那结果是什么？从根节点开始不断往左，第一个被访问的肯定是最左边的节点，然后访问该节点的右子树，最后向上回到父问题。因为每次访问最左的元素不止对一整棵二叉树成立，而是对所有子问题都成立，因此循环的时候自然最开始都是遍历到最左，然后访问，然后再进入右子树，我们可以用栈来实现回归父问题。

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

具体过程如下图所示： alt

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s; //辅助栈
        while(root != NULL || !s.empty()){ //当树节点不为空或栈中有节点时
            while(root != NULL){ //每次找到最左节点
                s.push(root);
                root = root->left;
            }
            TreeNode* node = s.top(); //访问该节点
            s.pop();
            res.push_back(node->val); 
            root = node->right; //进入右节点
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点数，遍历二叉树所有节点
空间复杂度： $O (n)$ ，辅助栈空间最大为链表所有节点数