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

题意：

• 返回二叉树的中序遍历序列。

方法一：递归

解题思路：

• 按照左子节点->根->右子节点的顺序，用递归的方式进行遍历。

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    //s存中序遍历结果
    vector<int> ans;
    //辅助函数
    void helper(TreeNode* root){
        if(root==nullptr)
            return;
        //中序递归遍历
        helper(root->left);
        ans.push_back(root->val);
        helper(root->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        helper(root);
        return ans;
    }
};

复杂度分析：

时间复杂度：，n为节点数量，每个节点遍历一次。
空间复杂度：，取决于递归层数，即树的深度，当二叉树退化为单链表时，时间复杂度最高为。

方法二：迭代

解题思路：

• 1.以迭代的方式遍历：首先要找到中序遍历的起始节点，如17-21行代码所示，将根节点root的左子节点循环入栈，直到整个二叉树最左的节点，该节点即为中序遍历的第一个节点。
• 2.用栈s存按照中序遍历顺序的节点，每次从栈中取出一个节点，即是当前时刻的根节点，将根节点的值加入到返回结果序列ans后，判断根节点的右子节点是否存在，若存在，则将该右子节点当做新的根节点，将该节点的左子节点循环入栈，类似1中的过程，1是整体的中序遍历，而此过程是局部的中序遍历。

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        //中序遍历序列返回结果
        vector<int> ans;
        //s存迭代下的遍历节点
        stack<TreeNode*> s;
        //将root的左节点循环入栈，直到找到最左的节点，也即是中序遍历的起始节点
        TreeNode* node1=root;
        while(node1){
            s.push(node1);
            node1=node1->left;
        }
        while(!s.empty()){
            //左->根->右 遍历至根
            TreeNode* cur=s.top();
            s.pop();
            ans.push_back(cur->val);
            //左->根->右 遍历至右，以右子节点为新的根节点，将该节点的左子节点循环入栈
            if(cur->right){
                TreeNode* tmp=cur->right;
                while(tmp){
                    s.push(tmp);
                    tmp=tmp->left;
                }
            }
        }
        return ans;
    }
};

图解如下：

复杂度分析：

时间复杂度：，n为节点数量，每个节点遍历一次。
空间复杂度：，栈s存遍历节点的顺序，最多为n。