2016.6.24——vector<vector<int>>【Binary Tree Level Order Traversal】

Binary Tree Level Order Traversal

本题收获：

1.vector<vector<int>>的用法

　　vector<vector<int> >注意<int>后面的空格，vector<vector<int>>表示的是二位向量。

　　输出格式（后面代码），不知道大小时，在vector中用push_back(vector<int>())

2.树用迭代

　　题目：

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

　　For example:
　　Given binary tree [3,9,20,null,null,15,7],

　　return its level order traversal as:

　　[
  　　[3],
  　　[9,20],
  　　[15,7]
　　]

　　思路：

　　　　：1.用vector<vector<int>>输出二位数组 2.迭代。

　　代码：

 1 vector<vector<int>> ret;
 2 
 3 void buildVector(TreeNode *root, int depth)
 4 {
 5     if(root == NULL) return;
 6     if(ret.size() == depth)
 7         ret.push_back(vector<int>());　　　　//depth的设置很巧妙
 8 
 9     ret[depth].push_back(root->val);
10     buildVector(root->left, depth + 1);
11     buildVector(root->right, depth + 1);
12 }
13 
14 vector<vector<int> > levelOrder(TreeNode *root) {
15     buildVector(root, 0);
16     return ret;
17 }

　　vector<vector<int>>输出格式：

 1 int n = res.size();
 2     for (int i = 0; i < n; i++)
 3     {
 4         int m = res[i].size();                //注意vector<vector<int> >的输出，以及size是怎么设定 
 5         for (int j = 0; j < m; j++)
 6         {
 7             cout << res[i][j] << " ";
 8         }
 9         cout << endl;                        //输出格式 cout << endl的位置
10     }

　　全部测试代码：

 1 // Binary Tree Level Order Traversal.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include "iostream"
 6 #include "malloc.h"
 7 #include "vector"
 8 using namespace std;
 9 
10 struct TreeNode
11 {
12     int val;
13     TreeNode *left, *right;
14     TreeNode(int x) : val(x), left(NULL), right(NULL){};
15 };
16 
17 class MyClass
18 {
19 public:
20     vector<vector<int> > res;
21     vector<vector<int>> levelOrder(TreeNode* root)
22     {
23         
24         buildvector(root, 0);
25         return  res;
26     }
27 
28     void buildvector(TreeNode* root, int depth)
29     {
30         if (root == NULL) return;
31         if (res.size() == depth)
32         {
33             res.push_back(vector<int>());
34         }
35 
36         res[depth].push_back(root->val);
37         buildvector(root->left, depth + 1);
38         buildvector(root->right, depth + 1);
39     }
40 };
41 
42 
43 
44 void creatTree(TreeNode* &T)
45 {
46     int data;
47     cin >> data;
48     if (data == -1)
49     {
50         T = NULL;
51     }
52     else
53     {
54         T = (TreeNode*)malloc(sizeof(TreeNode));
55         T->val = data;
56         creatTree(T->left);
57         creatTree(T->right);
58     }
59 }
60 
61 int _tmain(int argc, _TCHAR* argv[])
62 {
63     TreeNode* root = NULL;
64     creatTree(root);
65     vector<vector<int> > res;
66     MyClass solution;
67     res = solution.levelOrder(root);
68     int n = res.size();
69     for (int i = 0; i < n; i++)
70     {
71         int m = res[i].size();                //注意vector<vector<int> >的输出，以及size是怎么设定 
72         for (int j = 0; j < m; j++)
73         {
74             cout << res[i][j] << " ";
75         }
76         cout << endl;                        //输出格式
77     }
78     system("pause");
79     return 0;
80 }

　　3
   / 
  9  20
    /  
   15   7
上面的树，在本题作为输入为（3 9 -1 -1 20 15 -1 -1 7 -1 -1） 
-1代表后面没有子节点。