5.1.5—二叉树的遍历—Binary Tree Level Order Traversal II

描述
Given a binary tree, return the boom-up level order traversal of its nodes’ values. (ie, from le to
right, level by level from leaf to root).
For example: Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its boom-up level order traversal as:
[
[15,7]
[9,20],
[3],

]

#include "BinaryTree.h"
#include <stack>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
//===二叉树的层次遍历
vector<vector<int>> LevelTraversal2(BinaryTreeNode *proot)
{
queue<BinaryTreeNode*>temp;
vector<int> tempres;//记录所有数字
vector<int> num;//记录每一层的个数

temp.push(proot);
int Initial = 1;
num.push_back(Initial);

while (!temp.empty())
{
int cnt = 0;
for (int i = 0; i < Initial; i++)
{
BinaryTreeNode *p = temp.front();
tempres.push_back(p->m_nValue);
temp.pop();
if (p->m_pLeft)
{
temp.push(p->m_pLeft);
cnt++;
}
if (p->m_pRight)
{
temp.push(p->m_pRight);
cnt++;
}
}
Initial = cnt;
if (Initial!=0)
num.push_back(Initial);
}
//====================
vector<vector<int>> res;
int cnt = 0;
for (int i = 0; i < num.size();i++)
{
vector<int> cahe;
for (int j =cnt; j < cnt+num[i]; j++)
cahe.push_back(tempres[j]);

cnt += num[i];
res.push_back(cahe);
}
//=======================
reverse(res.begin(), res.end());
return res;
}
// ====================测试代码====================
//            8
//        6      10
//       5 7    9  11
int main()
{
BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
BinaryTreeNode* pNode9 = CreateBinaryTreeNode(9);
BinaryTreeNode* pNode11 = CreateBinaryTreeNode(11);

ConnectTreeNodes(pNode8, pNode6, pNode10);
ConnectTreeNodes(pNode6, pNode5, pNode7);
ConnectTreeNodes(pNode10, pNode9, pNode11);
//===
//PrintTree(pNode8);
//===
vector<vector<int>> res = LevelTraversal2(pNode8);
for (int i = 0; i < res.size(); i++)
{
for (int j = 0; j < res[i].size(); j++)
cout << res[i][j] << " ";
cout << endl;
}

DestroyTree(pNode8);
}