宽度搜索 leetcode 515

您需要在二叉树的每一行中找到最大的值。

示例：

输入: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

输出: [1, 3, 9]

思路：层序遍历的基础上，用一个容器存储每层中的元素值。对每层元素值进行排序以获取最大值。时间复杂度O(nlogn)（快排是O(logn)，快排嵌套在层序遍历中了，因此是O(nolgn)）

vector<int> largestValues(TreeNode* root) {
	vector<int> answer;
	if (root == nullptr) return answer;
	//存储每层节点的值
	vector<int>container;
	queue<TreeNode*> temp;
	temp.push(root);
	int size = 0;
	TreeNode* h = nullptr;
	//层序遍历
	while (!temp.empty()) {
		size = temp.size();
		while (size--) {
			h=temp.front();
			container.push_back(h->val);
			temp.pop();
			if (h->left != nullptr)
				temp.push(h->left);
			if(h->right != nullptr)
				temp.push(h->right);
		}
		//将每层节点值排序
		sort(container.begin(),container.end());
		answer.push_back(container.back());
		container.clear();
	}
	return answer;
}

优化：既然我们存的是每一层最大的值，为什么不直接用一个变量存呢？先存每层第一个节点的值，之后与本层中的其余节点进行比较，将每层的最大值存入数组中返回。这样就省去了把每层的每个值都存起来的空间，也省去的排序浪费的时间。做了这个改变，时间复杂度降为O(n)。

vector<int> largestValues(TreeNode* root) {
	vector<int> answer;
	if (root == nullptr) return answer;
	//存储每层节点第一个节点的值
	int larger = root->val;
	queue<TreeNode*> temp;
	temp.push(root);
	int size = 0;
	TreeNode* h = nullptr;
	//层序遍历
	while (!temp.empty()) {
		size = temp.size();
		//存储每层第一个节点的值
		larger = temp.front()->val;
		while (size--) {
			h = temp.front();
			if (h->val > larger)  larger = h->val;
			temp.pop();
			if (h->left != nullptr)
				temp.push(h->left);
			if (h->right != nullptr)
				temp.push(h->right);
		}
		answer.push_back(larger);
	}
	return answer;
}