一家专门做内部优惠的网站,丽水 网站建设,阿里云申请域名,南京seo排名外包1. 题目
给定一个二叉树#xff0c;检查它是否是镜像对称的。
例如#xff0c;二叉树 [1,2,2,3,4,4,3] 是对称的。1/ \2 2/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:1/ \2 2\ \3 3来源#xff1a;力扣#xff08;LeetCode#x…1. 题目
给定一个二叉树检查它是否是镜像对称的。
例如二叉树 [1,2,2,3,4,4,3] 是对称的。1/ \2 2/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:1/ \2 2\ \3 3来源力扣LeetCode 链接https://leetcode-cn.com/problems/symmetric-tree 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 递归
class Solution {
public:bool isSymmetric(TreeNode* root) {return sym(root,root);}bool sym(TreeNode *t1, TreeNode *t2){if((!t1t2)||(t1!t2))return false;else if(!t1!t2)return true;elsereturn(t1-valt2-val sym(t1-left,t2-right) sym(t1-right,t2-left));}
};2.2 循环
class Solution {
public:bool isSymmetric(TreeNode* root) {TreeNode *t1, *t2;queueTreeNode* q;q.push(root);q.push(root);while(!q.empty()){t1 q.front();q.pop();t2 q.front();q.pop();if((!t1t2)||(t1!t2))return false;else if(!t1!t2)continue;else//t1,t2都存在{if(t1-val ! t2-val)return false;q.push(t1-left);q.push(t2-right);q.push(t1-right);q.push(t2-left);}}return true;}
};《剑指Offer》同题面试题28. 对称的二叉树
递归
class Solution {bool ans true;
public:bool isSymmetric(TreeNode* root) {dfs(root,root);return ans;}void dfs(TreeNode* r1, TreeNode* r2){if(!ans || (!r1 !r2))return;if((!r1 r2)||(r1 !r2)){ans false;return;}if(r1-val ! r2-val)ans false;dfs(r1-left,r2-right);dfs(r1-right,r2-left);}
};循环
class Solution {
public:bool isSymmetric(TreeNode* root) {queueTreeNode* q;q.push(root);q.push(root);TreeNode *r1, *r2;while(!q.empty()){r1 q.front(); q.pop();r2 q.front(); q.pop();if((!r1 r2)||(r1 !r2))return false;if(r1 r2){if(r1-val ! r2-val)return false;q.push(r1-left);q.push(r2-right);q.push(r1-right);q.push(r2-left);}}return true;}
};
