公司网站域名解析谁来做,什么网站系统做的最好,中山网站搜索排名,wordpress怎么上传缩略图题目
给定一个二叉树#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; 你可以运用递归和迭代两种方法解决这个…题目
给定一个二叉树检查它是否是镜像对称的。
例如二叉树 [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
进阶 你可以运用递归和迭代两种方法解决这个问题吗
思路一超时
层序遍历然后如果该结点是空结点往该层子数组中填0否则填val 当此层所有结点都被遍历了(包括空结点)观察子数组是否对称。 然后更新queue如果该结点为空结点则它的子结点也是空结点如果该结点不是空结点它的子结点根据真实情况填如果为空也填入NULL。 不过这样好像超时了也就无法验证了。 退出循环的条件是该层的所有结点都是空结点
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {queueTreeNode* que;if(root!NULL) que.push(root);while(1){//该层结点元素个数 该层队列元素int size que.size();vectorint vec;int null_times0;//这里要使用固定大小的size不能使用que.size(),因为在处理中que.size是不断变化的//将这层元素送入队列中并依次从队首向队尾将元素出队列每个元素出队列的同时又将其不为空的子结点送入队列for(int i 0;isize;i){TreeNode* node que.front();//将队首元素送入该层结果que.pop();if(node!NULL) {vec.push_back(node-val);//将左右孩子结点入队列作为下一层的元素if(node-left!NULL) que.push(node-left);else que.push(NULL);if(node-right!NULL) que.push(node-right);else que.push(NULL);}else{null_times;vec.push_back(-2147483648);//将左右孩子结点入队列作为下一层的元素que.push(NULL);que.push(NULL);} }if(null_times size) break;int vecsizevec.size();for(int j0;jvecsize/21;j){if(vec[j]!vec[vecsize-1-j]) return false;}}return true;}
};思路二构造翻转二叉树判断是否相同
先构造一棵反转二叉树然后按顺序遍历这两棵树判断是否相同。 Leetcode226. 翻转二叉树(递归、迭代、层序三种解法) LeetCode 100. 相同的树 思考分析 不过此处有一个问题我们当时翻转二叉树的操作是在输入的二叉树上进行修改的。这样如果直接isSameTree(root,invertTree(root)); 得到的结果都是true。所以我们需要先深复制一个新的二叉树然后在新的二叉树上完成翻转操作然后将翻转后的二叉树与原本的二叉树进行判断。 关于深复制一棵二叉树 LintCode 375. 克隆二叉树(深复制)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* invertTree(TreeNode* root) {queueTreeNode* que;if(root!NULL) que.push(root);while(!que.empty()){int size que.size();for(int i 0;isize;i){TreeNode* node que.front();que.pop();TreeNode* tmp;tmp node-left;node-left node-right;node-right tmp;//将左右孩子结点入队列作为下一层的元素if(node-left) que.push(node-left);if(node-right) que.push(node-right);}}return root;}bool isSameTree(TreeNode* p, TreeNode* q) {if(p q){if(p-val q-val){return isSameTree(p-right,q-right) isSameTree(p-left,q-left);}else{return false;} }else if(!p !q){return true;}return false;}TreeNode * preorder(TreeNode * root){if(rootNULL) return NULL;TreeNode * ans;ansnew TreeNode(root-val);if(root-left!NULL){ans-leftpreorder(root-left);}if(root-right!NULL){ans-rightpreorder(root-right);}return ans;}bool isSymmetric(TreeNode* root) {TreeNode *roota;rootapreorder(root);return isSameTree(root,invertTree(roota));}
};参考其他思路
之前的构造的思路会导致空间严重浪费并且时间耗费也较多。 关于二叉树是否对称我们要比较的是根结点的左子树与右子树是不是相互翻转的。递归遍历的时候要同时遍历两棵树比较两棵子树的里侧和外侧元素是否相同。 本题的遍历顺序为后序遍历因为要通过递归函数的返回值来判断两个子树的内测结点与外侧结点是否相等。 一棵树遍历顺序为左右中另一棵树遍历顺序是右左中。这里可以理解为一种回溯的思想。
递归法
1、确定递归地参数和返回值 参数该结点的左子树结点、右子树结点 返回值bool类型 bool compare(TreeNode* left,TreeNode* right) 2、确定终止条件 1、左右都为空返回true 2、左右只有一个为空返回false 3、左右结点均不为空比较结点数值不相同返回false 4、左右结点均不为空数值相同返回true
if(left NULL rightNULL) return true;
else if(left!NULL rightNULL) return false;
else if(right!NULL leftNULL) return false;
else if(left-val ! right-val) return false;
3、确定单层递归逻辑 处理左右结点皆不为空且数值相同的情况。 1、比较二叉树外侧是否对称传入左结点的左孩子右结点的右孩子。 2、比较内侧是否对称传入左结点的右孩子右结点的左孩子。 3、如果左右都对称就返回true否则返回false
bool outside compare(left-left,right-right);
bool inside compare(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(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool compare(TreeNode* left,TreeNode* right){if(left NULL rightNULL) return true;else if(left!NULL rightNULL) return false;else if(right!NULL leftNULL) return false;else if(left-val ! right-val) return false;bool outside compare(left-left,right-right); bool inside compare(left-right,right-left);bool isSame outside inside; return isSame;}bool isSymmetric(TreeNode* root) {if(root NULL) return true;return compare(root-left,root-right);}
};迭代法
这一题的本质是判断两个树是否相互翻转并非简单的遍历。这里可以使用队列来比较两个树(根结点的左右子树)是否相互翻转。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {if(root NULL) return true;queueTreeNode* que;que.push(root-left); //将左子树头结点加入队列que.push(root-right); //将右子树头结点加入队列while(!que.empty()) //判断两个树是否翻转{TreeNode* leftNode que.front();que.pop();TreeNode* rightNode que.front();que.pop();if(!leftNode !rightNode) {//左右结点均为空说明此时是对称的continue;}//左右一个结点不为空或者都不为空但是数值不同返回falseif((!leftNode || !rightNode || (leftNode-val!rightNode-val))){return false;}//外侧que.push(leftNode-left); //左左que.push(rightNode-right); //右右//内侧que.push(leftNode-right);que.push(rightNode-left);}return true;}
};
