怎么自己免费创建一个网站,做电子签章登录那个网站,靖州建设局网站,成都画时网站建设226.翻转二叉树
题目链接#xff1a;226.翻转二叉树思路#xff1a;遍历二叉树#xff0c;遍历的时候交换左右节点即可代码#xff1a;
TreeNode* invertTree(TreeNode* root) {reverse(root);return root;}// 迭代法#xff0c;层序遍历void f2(TreeNode* root) {queue…226.翻转二叉树
题目链接226.翻转二叉树思路遍历二叉树遍历的时候交换左右节点即可代码
TreeNode* invertTree(TreeNode* root) {reverse(root);return root;}// 迭代法层序遍历void f2(TreeNode* root) {queueTreeNode* que;if (root ! NULL) 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;}// 递归法void reverse(TreeNode* root) {if(!root)return;TreeNode* l root-left;TreeNode* r root-right;reverse(l);reverse(r);root-left r;root-right l;}
101. 对称二叉树
题目链接101. 对称二叉树思路遍历的时候分别遍历比较左子树的右子树和右子树的做子树左子树的左子树和右子树的右子树对应即可代码
/*** 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:// 递归法bool isEqual(TreeNode* right, TreeNode* left) {if(!right || !left)return right left;return right-val left-val isEqual(right-left, left-right) isEqual(right-right, left-left);}// 迭代法bool isEqualIter(TreeNode* u, TreeNode* v) {queue TreeNode* q;q.push(u); q.push(v);while (!q.empty()) {u q.front(); q.pop();v q.front(); q.pop();if (!u !v) continue;if ((!u || !v) || (u-val ! v-val)) return false;q.push(u-left); q.push(v-right);q.push(u-right); q.push(v-left);}return true;}bool isSymmetric(TreeNode* root) {if(!root)return true;return isEqualIter(root-left, root-right);}
};
104.二叉树的最大深度
题目链接104.二叉树的最大深度思路遍历二叉树记录最大深度即可代码
class Solution {
public:// 递归法int maxRecur(TreeNode* root) {if (root nullptr) {return 0;}int l_depth maxDepth(root-left);int r_depth maxDepth(root-right);return max(l_depth, r_depth) 1;}// 迭代法层序遍历int maxIter(TreeNode* root) {if (root nullptr) return 0;queueTreeNode* Q;Q.push(root);int ans 0;while (!Q.empty()) {int sz Q.size();while (sz 0) {TreeNode* node Q.front();Q.pop();if (node-left) Q.push(node-left);if (node-right) Q.push(node-right);sz - 1;}ans 1;} return ans;}int maxDepth(TreeNode* root) {return maxRecur(root);}
};
111.二叉树的最小深度
题目链接111.二叉树的最小深度思路遍历二叉树记录最小深度相比最大深度这里记录最小深度时需要记录的是到叶子节点的最小深度需要比最大深度多两个判断代码
class Solution {
public:// 递归法int minDepthRecur(TreeNode *root) {if (root nullptr) {return 0;}if (root-right nullptr) {return minDepthRecur(root-left) 1; // 左子树的最小高度}if (root-left nullptr) {return minDepthRecur(root-right) 1; // 右子树的最小高度}return min(minDepthRecur(root-left), minDepthRecur(root-right)) 1;}// 迭代法层序遍历int minDepthIter(TreeNode *root) {if (root nullptr) return 0;queuepairTreeNode *, int que; // 记录节点和深度que.emplace(root, 1);while (!que.empty()) {TreeNode *node que.front().first;int depth que.front().second;que.pop();if (node-left nullptr node-right nullptr) {return depth; // 没有子树叶子节点最先到达的叶子节点的高度为最小深度}if (node-left ! nullptr) {que.emplace(node-left, depth 1); // 左子树的深度}if (node-right ! nullptr) { // 右子树的深度que.emplace(node-right, depth 1);}}return 0;}int minDepth(TreeNode *root) {return minDepthRecur(root);}
};
