一、题意
二、解答过程
这道题的思路就是： 把每个节点的左右孩子交换一下即可。
2.1递归法解答
递归法的三部曲：
- 确定递归函数的参数和返回值
- 确定终止条件
- 确定单层递归逻辑(采用前序遍历)
class Solution { public: TreeNode* invertTree(TreeNode* root) {//1.确定递归函数的参数和返回值 if(root==NULL) return root;//2.确定终止条件 swap(root->left,root->right);//3.确定单层逻辑 invertTree(root->left); invertTree(root->right); return root; } };
2.2迭代法解答
2.2.1迭代法模拟层次遍历
在之前我们学过了迭代法前序遍历代码如下：
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> que; if(root!=NULL) { que.push(root); } vector<vector<int>> result;//result二维向量数组 while(!que.empty()) { int size=que.size(); vector<int> vec; for(int i=0;i<size;i++) { TreeNode *node=que.front(); que.pop(); vec.push_back(node->val); if(node->left) que.push(node->left); if(node->right) que.push(node->right); } result.push_back(vec); } return result; } };
改一下代码，添加操作处理如下：
class Solution { public: //函数名要改 TreeNode* invertTree(TreeNode* root) { queue<TreeNode*> que; if(root!=NULL) { que.push(root); } vector<vector<int>> result;//result二维向量数组 while(!que.empty()) { int size=que.size(); // vector<int> vec; for(int i=0;i<size;i++) { TreeNode *node=que.front(); que.pop(); // vec.push_back(node->val); swap(node->left,node->right);//节点处理 if(node->left) que.push(node->left); if(node->right) que.push(node->right); } // result.push_back(vec); } //return result; return root; } };
