107. 二叉树的层序遍历 II

107. 二叉树的层序遍历 II

题目链接:107. 二叉树的层序遍历 II(中等)

题目描述

给定一个二叉树,返回其节点值自底向上的层序遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

例如: 给定二叉树 [3,9,20,null,null,15,7],

    3
  / \
9 20
  / \
  15   7

返回其自底向上的层序遍历为:

[
[15,7],
[9,20],
[3]
]

题解

思路:先做普通的层次遍历(从上到下,从左到右)102.二叉树的层序遍历,再将结果反转即可。

代码(C++):

//层次遍历2
vector<vector<int>> levelOrderBottom(TreeNode* root) {
    queue<TreeNode*> que;
    vector<vector<int>> result;
    if (root != nullptr) que.push(root);
    while (!que.empty()) {
        int size = que.size();
        vector<int> temp;
        for (int i = 0; i < size; i++) {
            TreeNode* node = que.front();
            que.pop();
            temp.push_back(node->val);
            if (node->left != nullptr) que.push(node->left);
            if (node->right != nullptr) que.push(node->right);
        }
        result.push_back(temp);
    }
    //将结果反转
    reverse(result.begin(), result.end());
    return result;
}

分析:

  • 时间复杂度:O(N),其中N是树中节点的个数,每个节点进出队列各一次

  • 空间复杂度:O(N),空间复杂度取决于队列开销,队列中的元素个数不超过N

上一篇:JZ77 按之字形顺序打印二叉树


下一篇:546-C++线程间的同步通信(生产者-消费者模型)