湖南商城网站建设,银川森林半岛,商标设计软件,wordpress关键词怎么设置力扣日记#xff1a;【二叉树篇】对称二叉树 日期#xff1a;2023.11.25 参考#xff1a;代码随想录、力扣 101. 对称二叉树
题目描述 难度#xff1a;简单 给你一个二叉树的根节点 root #xff0c; 检查它是否轴对称。
示例 1#xff1a; 输入#xff1a;root [1,…力扣日记【二叉树篇】对称二叉树 日期2023.11.25 参考代码随想录、力扣 101. 对称二叉树
题目描述 难度简单 给你一个二叉树的根节点 root 检查它是否轴对称。
示例 1 输入root [1,2,2,3,4,4,3] 输出true 示例 2 输入root [1,2,2,null,3,null,3] 输出false 提示
树中节点数目在范围 [1, 1000] 内-100 Node.val 100
进阶你可以运用递归和迭代两种方法解决这个问题吗
题解
/*** 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 {
#define SOLUTION 1
public:
#if SOLUTION 0bool isSymmetric(TreeNode* root) {/* // 错误的做法// 示例1前1234243, 中3241423, 后3424321层1223443// 示例2中12323层12233// 层序遍历不行只能中序遍历// 使用栈元素先进栈遇到相同的则弹出// 还是不能用值来判断是否对称....如果树上节点的值都是相等的那就无法判断了...stackint st_check; // 用来判断// 中序遍历左中右// 对于中序遍历访问和处理并不是同步进行的。而是先访问到最底层的左节点再开始处理入栈判断// 使用 cur 指针 先进行访问遍历// if (root NULL) return true;stackTreeNode* st; // 用来遍历TreeNode* cur root;while (cur ! NULL || !st.empty()) {if (cur ! NULL) { // 指针访问节点先遍历到最底层st.push(cur); // 将cur入栈cur cur-left; // 左} else { // 处理cur st.top(); // 中 (处理放入result数组)st.pop();if (cur ! root) { // 根节点不入栈判断if (st_check.empty() || st_check.top() ! cur-val) st_check.push(cur-val); // 空或不相等则入栈else st_check.pop(); // 相同则弹出}cur cur-right; // 右 (如果右节点不为空则在下次循环把右节点入栈否则从栈中弹出顶部节点)}}return st_check.empty(); */}
#elif SOLUTION 1 // 递归遍历/*思路判断二叉树是否对称 - 通过判断二叉树能否左右翻转分别比较外侧与内侧是否相等即左节点的外侧(左孩子)需与对应右节点的外侧(右孩子)相等内测同理采用的遍历方式为后序遍历 - 后序左右中 - 在左右子树都判断好是否能左右翻转后再将信息传递到父节点(中)中节点作为左孩子或右孩子又继续向上传递*/bool compare(TreeNode* left, TreeNode* right) { // 递归三要素1参数与返回值参数为当前层的左节点和对应右节点返回值为两者的子树能否相互翻转(注意是子树不包括自身尽管只有当左和对应右节点相等才有继续比较的必要)// 递归三要素2终止条件// 1) 左右都为空返回trueif (left NULL right NULL) return true;// 2) 左为空右不为空 或 左不为空右为空返回falseelse if ((left ! NULL right NULL) || (left NULL right ! NULL)) return false;// 3) 左右不为空且左右值不相等else if (left-val ! right-val) return false;// 递归三要素3处理逻辑如果左右值相等则递归向下判断else { // 由此可见左右子树均为后序遍历// 外侧bool outside compare(left-left, right-right); // 左子树左、 右子树右// 内侧bool inside compare(left-right, right-left); // 左子树右、 右子树左// 将外侧内侧的比较结果向上传递(给中节点)bool isSame outside inside; // 左子树中、 右子树中 逻辑处理return isSame; // 当外侧和内侧的子节点都分别相等则当前left和right的子树是可以翻转的}}bool isSymmetric(TreeNode* root) {return compare(root-left, root-right);}#elif SOLUTION 2 // 迭代法(队列)bool isSymmetric(TreeNode* root) {// 思路// 遍历将左侧节点和对应右侧节点成对放入队列// 处理再在弹出时成对弹出比较是否相等相等则继续遍历子节点否则终止queueTreeNode* q;if (root ! nullptr) { // 先把根节点的左右节点放入队列q.push(root-left);q.push(root-right);}while (!q.empty()) {// 成对弹出TreeNode* leftSide q.front(); q.pop();TreeNode* rightSide q.front(); q.pop();// 比较if (!leftSide !rightSide) continue; // 左右都为空(没有子节点则继续弹出)// 左右有一个为空 或 左右都不为空但不相等则肯定不对称返回falseelse if (!leftSide || !rightSide || (leftSide-val ! rightSide-val)) return false;// 如果相等则继续遍历将子节点入队列q.push(leftSide-left);q.push(rightSide-right); // 注意要成对左的左 与 右的右q.push(leftSide-right);q.push(rightSide-left); // 左的右 与 右的左}return true;}
#elif SOLUTION 3 // 迭代法(栈)bool isSymmetric(TreeNode* root) {// 思路与队列类似也是成对入栈、成对弹出、成对比较(队列更好理解……)stackTreeNode* st;if (root ! nullptr) { // 先把根节点的左右节点放入队列st.push(root-left);st.push(root-right);}while (!st.empty()) {// 成对弹出TreeNode* rightSide st.top(); st.pop();TreeNode* leftSide st.top(); st.pop(); // 比较if (!leftSide !rightSide) continue; // 左右都为空(没有子节点则继续弹出)// 左右有一个为空 或 左右都不为空但不相等则肯定不对称返回falseelse if (!leftSide || !rightSide || (leftSide-val ! rightSide-val)) return false;// 如果相等则继续遍历将子节点入队列st.push(leftSide-left);st.push(rightSide-right); // 注意要成对左的左 与 右的右st.push(leftSide-right);st.push(rightSide-left); // 左的右 与 右的左}return true;}
#endif
};复杂度
时间复杂度 空间复杂度
思路总结
