IT评测·应用市场-qidao123.com技术社区

标题: 刷题了：226.翻转二叉树 | 101. 对称二叉树 [打印本页]

---

作者: 不到断气不罢休    时间: 2024-7-31 04:45
标题: 刷题了：226.翻转二叉树 | 101. 对称二叉树
226.翻转二叉树

文章解说:https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频解说:https://www.bilibili.com/video/BV1sP4y1f7q7/?spm_id_from=333.788&vd_source=e70917aa6392827d1ccc8d85e19e8375
题目链接:https://leetcode.cn/problems/invert-binary-tree/description/
实现情况：
递归是什么什么顺序遍历呢？
前序和后续是最直接的
前序：

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10. * right(right) {}
11. * };
12. */
13. class Solution {
14. public:
15.     TreeNode* invertTree(TreeNode* root) {
16.         if (root == NULL)
17.             return root;
18.         swap(root->left, root->right); // 中
19.         invertTree(root->left);        // 左
20.         invertTree(root->right);       // 右
21.         return root;
22.     }
23. };

复制代码

后续

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10. * right(right) {}
11. * };
12. */
13. class Solution {
14. public:
15.     TreeNode* invertTree(TreeNode* root) {
16.         if (root == NULL)
17.             return root;
18.         
19.         invertTree(root->left);        // 左
20.         invertTree(root->right);       // 右
21.         swap(root->left, root->right); // 中
22.         return root;
23.     }
24. };

复制代码

中序不能直接全部通过，为什么？

下一次就是到遍历右孩子，发现这个是前想处理过的！
所以现在照旧须要处理左孩子

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10. * right(right) {}
11. * };
12. */
13. class Solution {
14. public:
15.     TreeNode* invertTree(TreeNode* root) {
16.         if (root == NULL)
17.             return root;
18.         invertTree(root->left);        // 左
19.         swap(root->left, root->right); // 中
20.         invertTree(root->left);       // 左（之前的右）
22.         return root;
23.     }
24. };

复制代码

101. 对称二叉树

文章解说:https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频解说:https://www.bilibili.com/video/BV1ue4y1Y7Mf/?spm_id_from=333.788&vd_source=e70917aa6392827d1ccc8d85e19e8375
题目链接:https://leetcode.cn/problems/symmetric-tree/description/
实现情况：

左孩子的左孩子要和右孩子的右孩子比
左孩子的右孩子要和右孩子的左孩子比

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10. * right(right) {}
11. * };
12. */
13. class Solution {
14. public:
15.     bool compare(TreeNode* left, TreeNode* right) {
16.         // 首先排除空节点的情况
17.         if (left == NULL && right != NULL)
18.             return false;
19.         else if (left != NULL && right == NULL)
20.             return false;
21.         else if (left == NULL && right == NULL)
22.             return true;
23.         else if (left->val != right->val)
24.             return false;
26.         bool outside = compare(left->left, right->right);
27.         bool inside = compare(left->right, right->left);
28.         bool isSame = outside && inside;
29.         return isSame;
30.     }
32.     bool isSymmetric(TreeNode* root) {
33.         if (root == NULL)
34.             return true;
35.         return compare(root->left, root->right);
36.     }
37. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4