BFS和DFS解二叉树的层序遍历 II

92 阅读 0 评论 61 点赞

我是靠谱客的博主懵懂万宝路，这篇文章主要介绍BFS和DFS解二叉树的层序遍历 II，现在分享给大家，希望可以做个参考。

BFS解法：

一层一层的遍历：

这道题我们仍然可以从上往下遍历，只不过遍历每一层的时候我们都把结果插入到列表的最前面，这样就达到了从下往上遍历的效果。

代码：

复制代码

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
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) 
    {
        vector<vector<int>> ve;
        //边界条件
        if(root==NULL)
        {
            return ve;
        }
        //队列
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            //v 用于储存每一层的数
            vector<int> v;
            int len=q.size();
            for(int i=0;i<len;i++)
            {
                TreeNode* temp=q.front();
                //出队
                q.pop();
                v.push_back(temp->val);
                //左右子节点如果不为空就加入到队列中
                if(temp->left!=NULL)
                {
                    q.push(temp->left);
                }
                if(temp->right!=NULL)
                {
                    q.push(temp->right);
                }
            }
            //把每层的值存储在v中，插入到ve最前面
            ve.insert(ve.begin(),v);
            
        }
        return ve;

    }
};

DFS解法：

DFS不会层层遍历，所以需要一个level 记录层数。每一层都有一个vector 容器存放每一层的节点值。

复制代码

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
class Solution {
public:
    vector<vector<int>> ve;
    void dfs(TreeNode* p,int level)
    {
        if(p!=NULL)
        {
            //如果level等于ve的长度，说明到下一层了，
            //并且下一层的vector还没有初始化，我们要
            //先初始化一个vector，然后插入进去到最前面。
            if(level==ve.size())
            {
                //在ve 前插入空vector
                ve.insert(ve.begin(),vector<int>(0));
            }
            //这里就相当于从后往前打印了
            ve[ve.size()-level-1].push_back(p->val);
            //当前节点访问完之后，再使用递归的方式分别访问当前节点的左右子节点
            dfs(p->left,level+1);
            dfs(p->right,level+1);
        }
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        dfs(root,0);
        return ve;
    }
};