[LeetCode] Binary Tree Level Order Traversal 2

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example: Given binary tree {3,9,20,#,#,15,7} ,

return its bottom-up level order traversal as:

[

  [15,7]

  [9,20],

  [3],

]

head.h里代码实现如下：

#include<vector>

#include<queue>

using namespace std;

#define NULL 0

struct TreeNode

{

	int val;

	TreeNode *left;

	TreeNode *right;

	TreeNode(int x):val(x),left(NULL),right(NULL) {}

};

struct Node

{

	TreeNode *node;

	int level;

	Node(){}

	Node(TreeNode *n,int l):node(n),level(l){}

};

class Solution

{

private:

	vector<vector<int> > ret;

	vector<vector<int> > retReverse;

public:

	vector<vector<int> > leverOrder(TreeNode *root)

	{

		ret.clear();

		if(root == NULL)

			return ret;

		queue<Node> q;

		q.push (Node(root,0));

		vector<int> a;

		int curLever = -1;

		while(!q.empty() )

		{

			Node node = q.front();

			if(node.node->left)

				q.push(Node(node.node->left,node.level+1));

			if(node.node->right)

				q.push(Node(node.node->right,node.level+1));

			if(curLever != node.level)

			{

				if(curLever != -1)

					ret.push_back(a);

				curLever = node.level ;

				a.clear();

				a.push_back(node.node->val);

			}

			else

				a.push_back(node.node->val);

			q.pop();

		}

		ret.push_back(a);

		retReverse.clear();

		for(int i=ret.size()-1;i>=0;i--)

			retReverse.push_back(ret[i]);

		return retReverse;

	}

};

main.cpp里代码实现如下：

#include"head.h"

#include<iostream>

int main()
{
 TreeNode *root;
 root=new TreeNode(3);
 root->left = new TreeNode(9);
 root->right =  new TreeNode(20);
 root->right->left =  new TreeNode(15);
 root->right->right =  new TreeNode(7);
 Solution sol;
 for(vector<vector<int> >::size_type ix=0;ix!=sol.leverOrder(root).size();++ix)
  {for(vector<int>::size_type i=0;i!=sol.leverOrder(root)[ix].size();++i)
       cout<<sol.leverOrder(root)[ix][i]<<" ";
      cout<<endl;}
 delete  root->right->right;
 delete  root->right->left;
 delete  root->right;
 delete  root->left;
 delete  root;
 return 0;
}