LeetCode145二叉树后序遍历

Posted on | | Visitors:
Words count in article: 937 字 | 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);
            traversal(root->right);
            result.push_back(root->val);
        }
    }

    vector<int> postorderTraversal(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> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> nodes;
        vector<int> result;
        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{
                nodes.push(root);
                nodes.push(nullptr);
                if(root->right!=nullptr)
                    nodes.push(root->right);
                if(root->left!=nullptr)
                    nodes.push(root->left);
            }
        }
        return result;
    }
};

题解三

解题思路

  • 栈法/迭代法

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

    用prev保存上1个遍历过的结点。对于1个根结点，分3步操作：

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

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

    2. 更新root为栈顶结点

      第1步结束后，此时栈顶结点无左子树或其左子树已遍历完

    3. 如果无右子树或右子树已遍历，则遍历root并更新prev为root、更新root为nullptr；否则root入栈并更新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
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> nodes;
        vector<int> result;
        TreeNode* prev=nullptr;
        while(root!=nullptr || !nodes.empty()){
            while(root!=nullptr){
                nodes.push(root);
                root=root->left;
            }
            root=nodes.top();
            nodes.pop();
            if(root->right==nullptr || root->right==prev){
                result.push_back(root->val);
                prev=root;
                root=nullptr;
            }else{
                nodes.push(root);
                root=root->right;
            }
        }
        return result;
    }
};

题解四

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

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

作者：@臭咸鱼

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

欢迎讨论和交流!