网站开发公司好开发客户吗,视频上传网站如何做,人跟狗做网站,新浪网站首页题目
原题链接 : 101.对称二叉树
题面 : 对于这一题呢#xff0c;题目要求给出递归和迭代两种方式来解决!!!
注 :
这一题不仅仅是判断左右两个子节点是否对称,而是要遍历两棵树而且要比较内侧和外侧节点
递归
先确认递归三要素 :
确定递归函数的参数和返回值
bool …题目
原题链接 : 101.对称二叉树
题面 : 对于这一题呢题目要求给出递归和迭代两种方式来解决!!!
注 :
这一题不仅仅是判断左右两个子节点是否对称,而是要遍历两棵树而且要比较内侧和外侧节点
递归
先确认递归三要素 :
确定递归函数的参数和返回值
bool cmp(TreeNode* left,TreeNode* right){}
确认终止条件
左节点和右结点一个非空那么一定不对称返回false;左右结点均为空那么对称返回true均不为空值不相等返回false,值相等返回下一步即继续向下递归
那么递归函数的整体代码也就写好了 : bool cmp(TreeNode* left,TreeNode* right){if(leftnullptr right!nullptr) return false;else if(left!nullptr rightnullptr) return false;else if(leftnullptr rightnullptr) return true;else if(left-val ! right-val) return false;else return cmp(left-left,right-right) cmp(left-right,right-left);}
确认递归的逻辑 :
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(leftnullptr right!nullptr) return false;else if(left!nullptr rightnullptr) return false;else if(leftnullptr rightnullptr) 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;queueTreeNode* 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) || (!lr)) 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
