Leetcode: Binary Tree Level Order Traversal II

题目

https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/

分析

Binary Tree Level Order Traversal一样, 只不过在最后把结果反转一下就行了。

代码

class Solution
{
public:
	vector<vector<int>> levelOrderBottom(TreeNode *root)
	{
		queue<TreeNode*> nodeQue;
		queue<int> depQue;
		TreeNode *node;
		int dep;
		int depBefore;
		vector<vector<int>> res;
		vector<int> solution;

		if (!root)
			return res;

		nodeQue.push(root);
		depQue.push(1);
		depBefore = 1;
		while (!nodeQue.empty())
		{
			node = nodeQue.front();
			nodeQue.pop();
			dep = depQue.front();
			depQue.pop();

			if (dep == depBefore)
				solution.push_back(node->val);
			else
			{
				res.push_back(solution);
				depBefore = dep;
				solution.clear();
				solution.push_back(node->val);
			}

			if (node->left)
			{
				nodeQue.push(node->left);
				depQue.push(dep + 1);
			}
			if (node->right)
			{
				nodeQue.push(node->right);
				depQue.push(dep + 1);
			}
		}
		res.push_back(solution);
		reverse(res.begin(), res.end());
		
		return res;
	}
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/38927307

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();