LeetCode94二叉树中序遍历

Posted on | | Visitors:
Words count in article: 881 字 | Reading time ≈ 4 分

[toc]

题目介绍

题解一

解题思路

  • 递归法

    先通过递归遍历当前根结点的左子树，然后遍历当前的根结点，然后通过递归遍历当前根结点的右子树。

  • 复杂度分析

    假设该二叉树有n个结点，则时间复杂度为$O(n)$、最大空间复杂度为$O(n)$、平均空间复杂度为$O(log\ n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> result;

    void traversal(TreeNode* root){
        if(root!=nullptr){
            traversal(root->left);
            result.push_back(root->val);
            traversal(root->right);
        }
    }

    vector<int> inorderTraversal(TreeNode* root) {
        traversal(root);
        return result;
    }
};

题解二

解题思路

  • 迭代法/栈法

    通过显式栈模拟递归函数。该思路仅需要微小改动就可以通用于二叉树的先/中/后序遍历。该思路实现3种顺序遍历的介绍：https://www.cnblogs.com/chouxianyu/p/13293284.html

    该思路的核心是将nullptr作为可以遍历下1个结点的标志（因此也就不能将空结点压入栈中），即遇到nullptr时就可以遍历下一个结点，如果不是nullptr则根据遍历顺序入栈，当前根结点入栈时也要将nullptr压入栈中（后续遇到这个nullptr时就可以遍历到该根结点）。

  • 复杂度分析

    假设二叉树有n个结点，则时间复杂度为$O(n)$、最大空间复杂度为$O(n)$、平均空间复杂度为$O(log\ n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> nodes;
        if(root!=nullptr)
            nodes.push(root);
        while(!nodes.empty()){
            root=nodes.top();
            nodes.pop();
            if(root==nullptr){
                result.push_back(nodes.top()->val);
                nodes.pop();
            }else{
                if (root->right!=nullptr)
                    nodes.push(root->right);
                nodes.push(root);
                nodes.push(nullptr);
                if (root->left!=nullptr)
                    nodes.push(root->left);
            }
        }
        return result;
    }
};

题解三

解题思路

  • 栈法/迭代法

    中序遍历的顺序为：左子树、根结点、右子树。

    对于1个根结点root，分3步操作：

    1. 将root压入栈中并不断更新为其左子树，直至root为空

      可以想象下，中序遍历时就是这样并不遍历当前结点，而是一直往左下角延伸到底

    2. 更新root为栈顶结点并遍历它（第1步结束后，此时栈顶结点无左子树或其左子树已遍历完）

    3. 更新root为其右子树通过循环遍历其右子树

      如果root非空或者栈非空则循环以上步骤

  • 复杂度分析

    假设二叉树有n个结点，则时间复杂度为$O(n)$、最大空间复杂度为$O(n)$、平均空间复杂度为$O(log\ n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> nodes;
        while(root!=nullptr || !nodes.empty()){
            while(root!=nullptr){
                nodes.push(root);
                root=root->left;
            }
            root=nodes.top();
            nodes.pop();
            result.push_back(root->val);
            root=root->right;
        }
        return result;
    }
};

题解四

Morris 遍历算法是另一种遍历二叉树的方法。

假设二叉树有n个结点，该算法的时间复杂度为$O(n)$、空间复杂度为$O(1)$。

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!