问题描述
LeetCode 226. 翻转二叉树
给一棵二叉树，用非递归的方式镜像翻转这棵二叉树。（输入为层次遍历）
输入：[1,2,3,4,5,6,7]
输出：[1,3,2,7,6,5,4]
C++代码 #include <iostream>#include <vector>#include <queue>using namespace std;struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode(int x):val(x), left(NULL), right(NULL){}};// 镜像二叉树void mirror(TreeNode* root) { queue<TreeNode *> que; que.push(root); while (!que.empty()) { TreeNode *current = que.front(); que.pop();// cout << current->val << endl; TreeNode *tmp = current->left; current->left = current->right; current->right = tmp; if(current->left != NULL){ que.push(current->left); } if(current->right != NULL){ que.push(current->right); } }}// 用层次遍历的数组创建一棵二叉树TreeNode* createTree(vector<int>& vec){ if(vec.size() == 0){ return NULL; } TreeNode* root = new TreeNode(vec[0]); queue<TreeNode*> que; que.push(root); int i = 0; while(!que.empty()){ TreeNode* current = que.front(); que.pop(); if(current == NULL){ i = i+2; }else{ if(++i < vec.size()){ current->left = new TreeNode(vec[i]); } if(++i < vec.size()) { current->right = new TreeNode(vec[i]); } que.push(current->left); que.push(current->right); } } return root;}// 层次遍历打印二叉树void printTree(TreeNode* root){ queue<TreeNode*> que; que.push(root); while(!que.empty()){ TreeNode* current = que.front(); que.pop(); if(current != NULL){ cout << current->val << " "; que.push(current->left); que.push(current->right); } } cout << endl;}int main(){ vector<int> vec = {1,2,3,4,5,6,7}; TreeNode* root = createTree(vec); printTree(root); mirror(root); printTree(root); return 0;} 代码分析
时间复杂度：O(n)，层次遍历一遍二叉树；
空间复杂度：O(log(n))，用队列保存的节点个数最多是树最底层的元素个数。