二叉树的中序遍历

问题描述：给定一个二叉树的根节点root，返回它的中序遍历。
示例1
输入值：{1,2,#,#,3}
返回值：[2,3,1]
说明：

示例2
输入：{}
返回值：[]
示例3
输入：{1,#,2}
返回值：[1,2]
说明：


方法一

思路分析

     首先我们可以考虑使用递归的办法，这也是最直接的办法。首先递归当问左子树，然后访问根节点，之后访问右子树，递归结束的条件为当前节点为空。

C++核心代码 

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        vector<int> temp;
        if(root==NULL)return temp;
        zhongxu(temp,root);
        return temp;
    }
    void zhongxu(vector<int>& temp,TreeNode* root)
    {
        if(root==NULL)return;//递归结束的条件
        zhongxu(temp,root->left);//递归访问左子树
        temp.push_back(root->val);//访问根节点
        zhongxu(temp,root->right);//递归访问右子树
    }
};

复杂度分析

  • 时间复杂度：递归算法的时间复杂度为递归的次数 * 每次递归中的操作次数，当给定的二叉树只有左子树或者只有右子树时递归复杂度最大为$n$，因此时间复杂度为$O(n)$
  • 空间复杂度：递归算法的空间复杂度为递归深度*每次递归的空间复杂度，当给定的二叉树只有左子树或者只有右子树时递归深度最大为$n$，因此空间复杂度为$O(n)$

方法二

思路分析

     上面的方法使用了递归的思想，因此我们可以使用栈的存储结构模拟递归的思想实现。 中序遍历的非递归方式实现思想是：
  • 初始化栈为空，从根结点开始，根节点入栈
  • 遍历左孩子同时压栈，当遍历结束，说明当前遍历的结点没有左孩子，从栈中取出来输出，
  • 然后访问该结点的右孩子，继续以上重复性的操作，直到栈为空程序结束。

图解



C++核心代码 

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        stack<TreeNode*> stk;
        vector<int> temp;
        while(!stk.empty()||root!=NULL)//栈不为空或者根节点不为空就一直遍历
        {
            while(root!=NULL)
            {
                stk.push(root);
                root=root->left;//不断的访问左子树并将根节点入栈
            }
            root=stk.top();//根节点为栈顶元素保存
            stk.pop();//栈顶元素出栈
            temp.push_back(root->val);//输出栈顶元素
            root=root->right;//访问根节点的右子树
            
        }
        return temp; 
    }
};

复杂度分析

  • 时间复杂度:不断的遍历寻找左子树，如果给的二叉树只有左子树或者只有右子树，那么时间复杂度最大为$O(n)$
  • 空间复杂度:借助于一个数组和一个栈，数组的大小为$n$，栈的大小最大的情况也是给的二叉树只有左子树或者只有右子树的情况，因此空间复杂度为$O(n)$