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

BFS解法：

一层一层的遍历：

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

代码：

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 容器 存放每一层的节点值。

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;
    }
};

总结：

从下往上遍历，我们只需要修改结果的位置即可，不一定需要从下往上记录节点值。

最后

以上就是懵懂万宝路为你收集整理的BFS和DFS解二叉树的层序遍历 II的全部内容，希望文章能够帮你解决BFS和DFS解二叉树的层序遍历 II所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。