BFS approach O(n) time and O(n) space


  • 0
    Z

    Level order traversal using BFS

    public:
    	vector<int> largestValues(TreeNode* root) {
    		queue<TreeNode*> q;
    		int level = 1;
    		vector<int>result;
                    if(!root) return result;
    		q.push(root);
    		while (!q.empty()) {
    			int qsize = q.size();
    			for (int i = 0; i < qsize; ++i) {
    				TreeNode* f = q.front();
    				q.pop();
    				if (result.size() < level) result.push_back(f->val);
    				else result[level - 1] = max(result[level-1], f->val);
    				if (f->left != nullptr)  q.push(f->left);
    				if (f->right != nullptr)  q.push(f->right);
    			}
    			level++;
    		}
    		return result;
    	}
    

Log in to reply
 

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