226.翻转二叉树
- 题目链接：226.翻转二叉树
- 思路：遍历二叉树，遍历的时候交换左右节点即可
- 代码：
TreeNode* invertTree(TreeNode* root) {reverse(root);return root;}// 迭代法，层序遍历void f2(TreeNode* root) {queue<TreeNode*> 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;queue<TreeNode*> 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;queue<pair<TreeNode *, 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);}
};
