首页 > 代码库 > leetcode - Binary Tree Level Order Traversal i ii

leetcode - Binary Tree Level Order Traversal i ii

题目:Binary Tree Level Order Traversal i ii

i和ii的差别仅在于最后将结果逆序一下就行了,算法上基本相同

 

个人思路:

1、二叉树的层次遍历,我们一层一层地处理,用一个队列(A队列)将每一层的所有节点按照从左到右的顺序入队

2、待该队列的所有节点都出队,并且用另外一个队列(B队列)接收出队的节点(为下一层节点的处理做准备),则考虑处理下一层节点

3、将B队列的节点逐个出队,考察节点的左孩子和右孩子,若存在则将孩子节点入A队列,如此循环地处理每一层节点,直到A队列为空结束

 

代码(注释中的代码为i的解):

  1 #include <stddef.h>  2 #include <queue>  3 #include <vector>  4 #include <deque>  5 #include <iostream>  6   7 using namespace std;  8   9 struct TreeNode 10 { 11     int val; 12     TreeNode *left; 13     TreeNode *right; 14     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 15 }; 16  17 class Solution 18 { 19 public: 20     vector<vector<int> > levelOrder(TreeNode *root) 21     { 22         /* 23         vector<vector<int> > total_result; 24         vector<int> level_result; 25         queue<TreeNode *> current_level; 26         queue<TreeNode *> current_level_bak; 27  28         if (root == NULL) 29         { 30             return total_result; 31         } 32  33         current_level.push(root); 34  35         while (!current_level.empty()) 36         { 37             TreeNode *current_node = current_level.front(); 38             current_level.pop(); 39             current_level_bak.push(current_node); 40             level_result.push_back(current_node->val); 41  42             if (current_level.empty()) 43             { 44                 total_result.push_back(level_result); 45                 level_result.clear(); 46                 while (!current_level_bak.empty()) 47                 { 48                     current_node = current_level_bak.front(); 49                     current_level_bak.pop(); 50                     if (current_node->left != NULL) 51                     { 52                         current_level.push(current_node->left); 53                     } 54                     if (current_node->right != NULL) 55                     { 56                         current_level.push(current_node->right); 57                     } 58                 } 59             } 60         } 61  62         return total_result; 63         */ 64  65         vector<vector<int> > total_result; 66         deque<vector<int> > temp_result; 67         vector<int> level_result; 68         queue<TreeNode *> current_level; 69         queue<TreeNode *> current_level_bak; 70  71         if (root == NULL) 72         { 73             return total_result; 74         } 75  76         current_level.push(root); 77  78         while (!current_level.empty()) 79         { 80             TreeNode *current_node = current_level.front(); 81             current_level.pop(); 82             current_level_bak.push(current_node); 83             level_result.push_back(current_node->val); 84  85             if (current_level.empty()) 86             { 87                 temp_result.push_front(level_result); 88                 level_result.clear(); 89                 while (!current_level_bak.empty()) 90                 { 91                     current_node = current_level_bak.front(); 92                     current_level_bak.pop(); 93                     if (current_node->left != NULL) 94                     { 95                         current_level.push(current_node->left); 96                     } 97                     if (current_node->right != NULL) 98                     { 99                         current_level.push(current_node->right);100                     }101                 }102             }103         }104 105         while (!temp_result.empty())106         {107             total_result.push_back(temp_result.front());108             temp_result.pop_front();109         }110 111         return total_result;112     }113 };114 115 int main()116 {117     TreeNode *root = new TreeNode(3);118     root->left = new TreeNode(9);119     root->right = new TreeNode(20);120     root->right->left = new TreeNode(15);121     root->right->right = new TreeNode(7);122 123     Solution s;124     vector<vector<int> > result = s.levelOrder(root);125 126     for (int i = 0; i < result.size(); ++i)127     {128         vector<int> level = result[i];129         for (int j = 0; j < level.size(); ++j)130         {131             cout << level[j] << ",";132         }133         cout << endl;134     }135 136     system("pause");137 138     return 0;139 }
View Code

 

网上的思路也大致是这样