剑指offer | 32 - II. 从上到下打印二叉树 II

我不是女神ヾ 2022-12-28 01:42 108阅读 0赞

**题目内容**

> 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

**例如:**

给定二叉树: [3,9,20,null,null,15,7],
    
        3
       / \
      9  20
        /  \
       15   7
    
    返回其层次遍历结果：
    
    [
      [3],
      [9,20],
      [15,7]
    ]

**提示：**

节点总数 <= 1000

--------------------

方法一：DFS

class Solution { 
    public:
        vector<vector<int>> levelOrder(TreeNode* root) { 
            vector<vector<int>> res;
            dfs(root,res,0);
            return res;
        }
        void dfs(TreeNode* root,vector<vector<int>>& res,int level)//一定要引用，不然就要维护全局变量了。
        { 
            if(!root) return;
            if(level>=res.size()) res.emplace_back(vector<int>());
            res[level].emplace_back(root->val);
            dfs(root->left,res,level+1);
            dfs(root->right,res,level+1);
        }
    };

方法二：BFS

class Solution { 
    public:
        vector<vector<int>> levelOrder(TreeNode* root) { 
            queue<TreeNode*> q;
            q.push(root);
            vector<vector<int>> res;
            while(q.size())
            { 
                int size=q.size();
                vector<int> level;
                for(int i=0;i<size;i++)
                { 
                    TreeNode* rt=q.front();q.pop();
                    if(!rt) continue;
                    level.push_back(rt->val);
                    if(rt->left) q.push(rt->left);
                    if(rt->right) q.push(rt->right);
                }
                if(level.size()!=NULL) res.push_back(level);
            }
            return res;
        }
    };