BFS + DFS


  • 0
    N

    BFS

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

    DFS

    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>> res;
            dfs(root, 0, res);
            return res;
        }
        
        void dfs(TreeNode* root, int depth, vector<vector<int>>& res) {
            if (!root) return;
            if (depth == res.size()) {
                vector<int> tmp(1, root->val);
                res.push_back(tmp);
            } else {
                res[depth].push_back(root->val);
            }
            
            dfs(root->left, depth + 1, res);
            dfs(root->right, depth + 1, res);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.