首页 > itarticle > leetcode226:二叉树的层次遍历

leetcode226:二叉树的层次遍历

admin 11月 13, 2020 0

摘要：二叉树的层次遍历。

Problem：

二叉树的层次遍历。不同的是返回结果要分层，每层的值为一个vector。

解法一：递归


 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class  {
private:
    vector<vector<int>> ans;

public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        levelOrder2(root, 0);
        return ans;
    }
    
    void levelOrder2(TreeNode* root, int level){
        if(!root) return;
        if(ans.size() == level) ans.push_back({});
        ans[level].push_back(root -> val);
        levelOrder2(root -> left, level+1);
        levelOrder2(root -> right, level+1);
    }
};

解法二：非递归


 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class  {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root) return {};
        vector< vector<int> > ans;
        queue <TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            vector<int> tmp;
            int len = q.size();
            for(int i=0; i<len; i++){
                TreeNode* node = q.front();
                q.pop();
                tmp.push_back(node -> val);
                if(node -> left) q.push(node -> left);
                if(node -> right) q.push(node -> right);
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};