這三題都是二叉樹的層次遍歷，就放一起吧~
Binary Tree Level Order Traversal：裸的層次遍歷，BFS之
1 /**
2 * Definition for binary tree
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 struct Que {
13 TreeNode *pt;
14 int depth;
15 }que[10010];
16 vector<vector<int> > levelOrder(TreeNode *root) {
17 vector<vector<int> > res;
18 if(root == NULL) return res;
19 int l = 0, r = 1, tdepth = 0;
20 que[0].pt = root;
21 que[0].depth = 0;
22 vector<int> tres;
23 tres.push_back(root->val);
24 res.push_back(tres);
25 tres.clear();
26 while(l < r) {
27 TreeNode *tp = que[l].pt;
28 if(tdepth < que[l].depth) {
29 res.push_back(tres);
30 tres.clear();
31 }
32 if(tp->left != NULL) {
33 que[r].pt = tp->left;
34 que[r].depth = que[l].depth + 1;
35 tres.push_back(tp->left->val);
36 ++r;
37 }
38 if(tp->right != NULL) {
39 que[r].pt = tp->right;
40 que[r].depth = que[l].depth + 1;
41 tres.push_back(tp->right->val);
42 ++r;
43 }
44 tdepth = que[l].depth;
45 ++l;
46 }
47 if(!tres.empty()) res.push_back(tres);
48 return res;
49 }
50 };
Binary Tree Zigzag Level Order Traversal：二叉樹之字形的層次遍歷，加一個(gè)記錄節(jié)點(diǎn)深度的變量，然后根據(jù)深度的奇偶改變遍歷后結(jié)果的存儲(chǔ)順序就行
1 /**
2 * Definition for binary tree
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 struct Que {
13 TreeNode *pt;
14 int depth;
15 }que[10010];
16 vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
17 vector<vector<int> > res;
18 if(root == NULL) return res;
19 int l = 0, r = 1, tdepth = 0;
20 que[0].pt = root;
21 que[0].depth = 0;
22 vector<int> tres;
23 tres.push_back(root->val);
24 res.push_back(tres);
25 tres.clear();
26 while(l < r) {
27 TreeNode *tp = que[l].pt;
28 if(tdepth < que[l].depth) {
29 if(!(tdepth & 1)) reverse(tres.begin(), tres.end());
30 res.push_back(tres);
31 tres.clear();
32 }
33 if(tp->left != NULL) {
34 que[r].pt = tp->left;
35 que[r].depth = que[l].depth + 1;
36 tres.push_back(tp->left->val);
37 ++r;
38 }
39 if(tp->right != NULL) {
40 que[r].pt = tp->right;
41 que[r].depth = que[l].depth + 1;
42 tres.push_back(tp->right->val);
43 ++r;
44 }
45 tdepth = que[l].depth;
46 ++l;
47 }
48 if(!tres.empty()) {
49 if(tdepth & 1) reverse(tres.begin(), tres.end());
50 res.push_back(tres);
51 }
52 return res;
53 }
54 };
Maximum Depth of Binary Tree：層次遍歷二叉樹求最大深度就行
1 /**
2 * Definition for binary tree
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 struct Que {
13 TreeNode *pt;
14 int depth;
15 }que[10010];
16 int maxDepth(TreeNode *root) {
17 if(root == NULL) return 0;
18 int l = 0, r = 1;
19 que[0].pt = root;
20 que[0].depth = 1;
21 while(l < r) {
22 TreeNode *tp = que[l].pt;
23 if(tp->left != NULL) {
24 que[r].pt = tp->left;
25 que[r].depth = que[l].depth + 1;
26 ++r;
27 }
28 if(tp->right != NULL) {
29 que[r].pt = tp->right;
30 que[r].depth = que[l].depth + 1;
31 ++r;
32 }
33 ++l;
34 }
35 return que[r - 1].depth;
36 }
37 };