题目：Binary Tree Level Order Traversal i ii
i和ii的差别仅在于最后将结果逆序一下就行了，算法上基本相同
个人思路：
1、二叉树的层次遍历，我们一层一层地处理，用一个队列（A队列）将每一层的所有节点按照从左到右的顺序入队
2、待该队列的所有节点都出队，并且用另外一个队列（B队列）接收出队的节点（为下一层节点的处理做准备），则考虑处理下一层节点
3、将B队列的节点逐个出队，考察节点的左孩子和右孩子，若存在则将孩子节点入A队列，如此循环地处理每一层节点，直到A队列为空结束
代码（注释中的代码为i的解）：
1 #include2 #include 3 #include 4 #include 5 #include 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 > levelOrder(TreeNode *root) 21 { 22 /* 23 vector > total_result; 24 vector level_result; 25 queue current_level; 26 queue 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 > total_result; 66 deque > temp_result; 67 vector level_result; 68 queue current_level; 69 queue 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 > result = s.levelOrder(root);125 126 for (int i = 0; i < result.size(); ++i)127 {128 vector 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 }
网上的思路也大致是这样