101. 对称二叉树

题目

原题链接 : 101.对称二叉树

题面 : 

 对于这一题呢，题目要求给出递归和迭代两种方式来解决!!!

注 : 

• 这一题不仅仅是判断左右两个子节点是否对称,而是要遍历两棵树而且要比较内侧和外侧节点

递归

先确认递归三要素 : 

1. 确定递归函数的参数和返回值

bool cmp(TreeNode* left,TreeNode* right){}

1. 确认终止条件

• 左节点和右结点一个非空，那么一定不对称，返回false;
• 左右结点均为空，那么对称，返回true
• 均不为空，值不相等，返回false,值相等，返回下一步，即继续向下递归

那么递归函数的整体代码也就写好了 : 

    bool cmp(TreeNode* left,TreeNode* right){if(left==nullptr && right!=nullptr) return false;else if(left!=nullptr && right==nullptr) return false;else if(left==nullptr && right==nullptr) return true;else if(left->val != right->val) return false;else return cmp(left->left,right->right) && cmp(left->right,right->left);}

1. 确认递归的逻辑 : 

bool outside = cmp(left->left, right->right);   // 左子树：左、 右子树：右
bool inside = cmp(left->right, right->left);    // 左子树：右、 右子树：左
bool isSame = outside && inside;                    // 左子树：中、 右子树：中（逻辑处理）
return isSame;

那么题解代码也就出来了 : 

/*** 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 cmp(TreeNode* left,TreeNode* right){if(left==nullptr && right!=nullptr) return false;else if(left!=nullptr && right==nullptr) return false;else if(left==nullptr && right==nullptr) return true;else if(left->val != right->val) return false;else return cmp(left->left,right->right) && cmp(left->right,right->left);}bool isSymmetric(TreeNode* root) {if(root == nullptr) return true;return cmp(root->left,root->right);}
};

 

迭代

迭代的思路和想法与递归相同，这里呢，就用queue队列来模拟

详细请看代码 :

/*** 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 isSymmetric(TreeNode* root) {if(root == nullptr) return true;queue<TreeNode*> que;que.push(root->left);que.push(root->right);while(!que.empty()){TreeNode* l = que.front();que.pop();TreeNode* r = que.front();que.pop();if(!l && !r) continue;//左右结点均为空，直接下一步;if((l&&!r) || (!l&&r)) return false;//左右结点一个为空，返回false;if(l->val != r->val) return false;//均不为空但不相等，直接返回false;que.push(l->left);que.push(r->right);que.push(l->right);que.push(r->left);}return true;}
};

最后看完，能给个赞吗,hh！！！