广东外贸网站推广,分类wordpress,成都网站建设常凡云,潍坊中小型网站建设公司翻转二叉树 理解题意#xff0c;翻转即每个结点的左右子树翻转/对调题解1 递归——自下而上题解2 迭代——自上而下 给你一棵二叉树的根节点
root #xff0c;翻转这棵二叉树#xff0c;并返回其根节点。 提示#xff1a;
树中节点数目范围在 [0, 100] 内-100 Node.… 翻转二叉树 理解题意翻转即每个结点的左右子树翻转/对调题解1 递归——自下而上题解2 迭代——自上而下 给你一棵二叉树的根节点
root 翻转这棵二叉树并返回其根节点。 提示
树中节点数目范围在 [0, 100] 内-100 Node.val 100
理解题意翻转即每个结点的左右子树翻转/对调
题解1 递归——自下而上
/*** 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) return nullptr;TreeNode* LEFT(nullptr), *RIGHT(nullptr);/** 递归思路最后翻转的树 翻转后的左子树 翻转后的右子树有左子树翻转左子树有右子树翻转右子树每次翻转的步骤一致所以符合递归思路**/if(root-left)LEFT invertTree(root-left);if(root-right) RIGHT invertTree(root-right);root-left RIGHT;root-right LEFT;return root;}
};题解2 迭代——自上而下
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(! root) return nullptr;// 换成stack按自上而下思路逻辑一致queueTreeNode* Que;Que.push(root);while(Que.size()){TreeNode* tmp Que.front();Que.pop();TreeNode* left tmp-left;TreeNode* right tmp-right;if(left) Que.push(left);if(right) Que.push(right);tmp-left right;tmp-right left;}return root;}
};
