LeetCode144二叉树前序遍历

Posted on | | Visitors:
Words count in article: 830 字 | 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
class Solution{
public:
    vector<int> result;

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

题解二

解题思路

  • 栈法/迭代法

    显式地模拟递归函数的栈，每次结点出栈后相当于调用1次递归函数（处理1个根结点及其子树），出栈后根据遍历顺序对当前根结点及其左右子树进行操作（注意遍历顺序和入栈顺序是相反的）。

  • 复杂度分析

    假设二叉树有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
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> nodes;
        nodes.push(root);

        while(!nodes.empty()){
            root = nodes.top();
            nodes.pop();
            if (root!=nullptr){
                result.push_back(root->val);
                nodes.push(root->right);
                nodes.push(root->left);
            }
        }

        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
26
27
28
class Solution {
public:
    vector<int> preorderTraversal(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);
                if (root->left!=nullptr)
                    nodes.push(root->left);
                nodes.push(root);
                nodes.push(nullptr);
            }
        }

        return result;
    }
};

题解四

还有个Morris遍历，其时间复杂度为$O(n)$、空间复杂度为$O(1)$，其核心是利用树中的大量空闲指针，实现空间开销的缩减。该方法的论文名称为Traversing Binary Trees Simply and Cheaply。

作者：@臭咸鱼

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

欢迎讨论和交流!