权威的手机网站制作,网络营销的现状,wordpress用什么数据库,竞价单页网站制作教程LeetCode 226.翻转二叉树
1、题目
题目链接#xff1a;226. 翻转二叉树 给你一棵二叉树的根节点 root #xff0c;翻转这棵二叉树#xff0c;并返回其根节点。
示例 1#xff1a;
输入#xff1a;root [4,2,7,1,3,6,9]
输出#xff1a;[4,7,2,9,6,3,1]示例 2#…LeetCode 226.翻转二叉树
1、题目
题目链接226. 翻转二叉树 给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。
示例 1
输入root [4,2,7,1,3,6,9]
输出[4,7,2,9,6,3,1]示例 2
输入root [2,1,3]
输出[2,3,1]示例 3
输入root []
输出[]提示
树中节点数目范围在 [0, 100] 内-100 Node.val 100
2、递归前序遍历
思路
我们从根节点开始翻转先交换左右孩子节点然后翻转左子树最后翻转右子树。即可完成以 root 为根节点的整棵子树的翻转。
代码
#include iostreamusing namespace std;//Definition for a binary tree node.
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {public:TreeNode* invertTree(TreeNode* root) {// 如果根节点为空则返回空指针if (root nullptr) {return nullptr;}// 交换左右子树swap(root-left, root-right);// 递归翻转左子树invertTree(root-left);// 递归翻转右子树invertTree(root-right);// 返回翻转后的根节点return root;}
};int main() {TreeNode* root new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(7, new TreeNode(6), new TreeNode(9)));Solution s;TreeNode* res s.invertTree(root);cout res-val endl;cout res-left-val endl;cout res-right-val endl;cout res-left-left-val endl;cout res-left-right-val endl;cout res-right-left-val endl;cout res-right-right-val endl;delete root;return 0;
}复杂度分析
时间复杂度O(N)其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点对每个节点而言我们在常数时间内交换其两棵子树。空间复杂度O(N)。使用的空间由递归栈的深度决定它等于当前节点在二叉树中的高度。在平均情况下二叉树的高度与节点个数为对数关系即 O(logN)。而在最坏情况下树形成链状空间复杂度为 O(N)。
3、递归中序遍历
思路
注意写中序遍历的时候不能仅仅只是将前序遍历的代码顺序调整一下。 因为在“中序遍历”的时候左右子树已经交换过了因此原来写 invertTree(root.right); 的地方应该写作 invertTree(root.left);。
代码
class Solution {
public:TreeNode* invertTree(TreeNode* root) {// 如果根节点为空则返回空指针if (root nullptr) {return nullptr;}// 递归翻转左子树invertTree(root-left);// 交换左右子树swap(root-left, root-right);// 递归翻转右子树invertTree(root-left);// 返回反转后的根节点return root;}
};复杂度分析
时间复杂度O(N)其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点对每个节点而言我们在常数时间内交换其两棵子树。空间复杂度O(N)。使用的空间由递归栈的深度决定它等于当前节点在二叉树中的高度。在平均情况下二叉树的高度与节点个数为对数关系即 O(logN)。而在最坏情况下树形成链状空间复杂度为 O(N)。
4、递归后序遍历
思路
我们从根节点开始递归地对树进行遍历并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转那么我们只需要交换两棵子树的位置即可完成以 root 为根节点的整棵子树的翻转。
代码
class Solution {
public:TreeNode* invertTree(TreeNode* root) {// 如果根节点为空则返回空指针if (root nullptr) {return nullptr;}// 递归翻转左子树invertTree(root-left);// 递归翻转右子树invertTree(root-right);// 交换左右子树swap(root-left, root-right);// 返回反转后的根节点return root;}
};复杂度分析
时间复杂度O(N)其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点对每个节点而言我们在常数时间内交换其两棵子树。空间复杂度O(N)。使用的空间由递归栈的深度决定它等于当前节点在二叉树中的高度。在平均情况下二叉树的高度与节点个数为对数关系即 O(logN)。而在最坏情况下树形成链状空间复杂度为 O(N)。
5、迭代法前序遍历
代码
class Solution {
// 迭代法(前序遍历)使用栈先将根节点入栈然后不断弹出栈顶节点交换其左右子树并将右子树、左子树入栈直到栈为空
public:TreeNode* invertTree(TreeNode* root) {// 如果根节点为空则直接返回空if (root nullptr) return nullptr;// 创建一个栈用于存储待处理的节点stackTreeNode* stk;// 将根节点入栈stk.push(root);// 当栈不为空时循环处理栈中的节点while(!stk.empty()) {// 取出栈顶节点TreeNode* node stk.top();// 将栈顶节点出栈stk.pop();// 交换当前节点的左右子树swap(node-left, node-right);// 如果当前节点的右子树不为空则将右子树入栈if(node-right) stk.push(node-right);// 如果当前节点的左子树不为空则将左子树入栈if(node-left) stk.push(node-left);}// 返回根节点return root;}
};复杂度分析
时间复杂度O(N)其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点对每个节点而言我们在常数时间内交换其两棵子树。空间复杂度O(N)。使用的空间由递归栈的深度决定它等于当前节点在二叉树中的高度。在平均情况下二叉树的高度与节点个数为对数关系即 O(logN)。而在最坏情况下树形成链状空间复杂度为 O(N)。
6、迭代法中序遍历
代码
class Solution {
// 迭代法(中序遍历)使用栈先将根节点入栈然后不断弹出栈顶节点交换其左右子树并将右子树、左子树入栈直到栈为空public:TreeNode* invertTree(TreeNode* root) {stackTreeNode* stk;if (root ! nullptr) {stk.push(root);}while (!stk.empty()) {TreeNode* node stk.top();if (node ! nullptr) {stk.pop();// 将右子节点入栈if (node-right) {stk.push(node-right);}// 将当前节点再次入栈用于后续交换左右子节点stk.push(node);stk.push(nullptr);// 将左子节点入栈if (node-left) {stk.push(node-left);}} else {stk.pop();// 取出需要交换的节点node stk.top();stk.pop();// 交换左右子节点swap(node-left, node-right);}}return root;}
};复杂度分析
时间复杂度O(N)其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点对每个节点而言我们在常数时间内交换其两棵子树。空间复杂度O(N)。使用的空间由递归栈的深度决定它等于当前节点在二叉树中的高度。在平均情况下二叉树的高度与节点个数为对数关系即 O(logN)。而在最坏情况下树形成链状空间复杂度为 O(N)。
7、迭代法后序遍历
代码
class Solution {
// 迭代法(后序遍历)使用栈先将根节点入栈然后不断弹出栈顶节点并将右子树、左子树入栈交换其左右子树直到栈为空
public:TreeNode* invertTree(TreeNode* root) {// 如果根节点为空则直接返回空if (root nullptr) return nullptr;// 创建一个栈用于存储待处理的节点stackTreeNode* stk;// 将根节点入栈stk.push(root);// 当栈不为空时循环处理栈中的节点while(!stk.empty()) {// 取出栈顶节点TreeNode* node stk.top();// 将栈顶节点出栈stk.pop();// 如果当前节点的右子树不为空则将右子树入栈if(node-right) stk.push(node-right);// 如果当前节点的左子树不为空则将左子树入栈if(node-left) stk.push(node-left);// 交换当前节点的左右子树swap(node-left, node-right);}// 返回根节点return root;}
};复杂度分析
时间复杂度O(N)其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点对每个节点而言我们在常数时间内交换其两棵子树。空间复杂度O(N)。使用的空间由递归栈的深度决定它等于当前节点在二叉树中的高度。在平均情况下二叉树的高度与节点个数为对数关系即 O(logN)。而在最坏情况下树形成链状空间复杂度为 O(N)。
8、层序遍历广度优先遍历
思路
层序遍历也可以把每个节点的左右孩子都翻转一遍我们可以使用队列将根节点入队列然后不断弹出队列头节点交换其左右子树并将右子树、左子树入队列直到队列为空。
代码
class Solution {
// 层序遍历使用队列将根节点入队列然后不断弹出队列头节点交换其左右子树并将右子树、左子树入队列直到队列为空
public:TreeNode* invertTree(TreeNode* root) {// 创建一个队列用于存储待处理的节点queueTreeNode* que;// 如果根节点不为空则将其加入队列if (root ! nullptr) que.push(root);// 当队列不为空时循环处理队列中的节点while (!que.empty()) {// 记录当前队列的大小int size que.size();// 遍历当前队列中的所有节点for (int i 0; i size; i) {// 取出队列中的节点TreeNode* node que.front();// 将节点从队列中移除que.pop();// 交换节点的左右子树swap(node-left, node-right);// 如果节点的左子树不为空则将其加入队列if (node-left) que.push(node-left);// 如果节点的右子树不为空则将其加入队列if (node-right) que.push(node-right);}}// 返回处理后的根节点return root;}
};复杂度分析
时间复杂度O(N)其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点对每个节点而言我们在常数时间内交换其两棵子树。空间复杂度O(N)。使用的空间由递归栈的深度决定它等于当前节点在二叉树中的高度。在平均情况下二叉树的高度与节点个数为对数关系即 O(logN)。而在最坏情况下树形成链状空间复杂度为 O(N)。
