Fork me on GitHub

leetcode之107. 二叉树的层次遍历 II

发表于 | 分类于
字数统计 597 字 | 阅读时长 2 分钟

题目描述：

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

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

1
2
3
4
5
6
>     3
>    / \
>   9  20
>     /  \
>    15   7
>

返回其自底向上的层次遍历为：

1
2
3
4
5
6
> [
>   [15,7],
>   [9,20],
>   [3]
> ]
>

解题思路一：

时间复杂度：${O(n^2)}$,空间复杂度：$O(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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
    	//定义一个队列
        queue<TreeNode *> q;
        //定义一个二维数组
        vector<vector<int> > vec;
        
        //根结点为空的话就直接返回
        if(!root) return vec;
        
        //根结点不为空就把它放入队列里面
        q.push(root);
        while(!q.empty())
        {
        	//定义一个一维数组
            vector<int> temp;
            //定义队列的长度
            int size_ = q.size();
            //循环遍历队列中的值
            for(int i = 0; i < size_; i++)
            {
            	//把队列中的第一个元素放入到t中
                TreeNode *t = q.front();
                //删除队列中的第一个元素
                q.pop();
                //把队列中第一个元素放到一维数组中
                temp.push_back(t->val);
                //如果树节点的左节点不为空，就把它放到队列中
                if(t->left) q.push(t->left);
                //如果树节点的右节点不为空，就把它放到队列中
                if(t->right) q.push(t->right);
            }
            //把一维数组给二维数组
            vec.push_back(temp);   
            //清除一维数组
            temp.clear();     
        }
        //二维数组中的数反转就是我们要求的数
        reverse(vec.begin(),vec.end());
        return vec;
    }
};

解题思路二：

时间复杂度：${O(n^2)}$,空间复杂度：$O(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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode *> q;
        vector<vector<int> > vec;
        stack<vector<int> > st;
        
        if(!root) return vec;
        
        q.push(root);
        while(!q.empty())
        {
            vector<int> temp;
            int size_ = q.size();
            for(int i = 0; i < size_; i++)
            {
                TreeNode *t = q.front();
                q.pop();
                temp.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            st.push(temp);   
            temp.clear();     
        }
        while(!st.empty())
        {
            vec.push_back(st.top());
            st.pop();
        }
        return vec;
    }
};