Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
这三题都是二叉树的层次遍历,就放一起吧~
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:二叉树之字形的层次遍历,加一个记录节点深度的变量,然后根据深度的奇偶改变遍历后结果的存储顺序就行
 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 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理