摘要:文章目录一剑指二叉树的镜像剑指二叉树的镜像思路递归二剑指对称的二叉树剑指对称的二叉树思路递归三剑指二叉树的深度剑指二叉树的深度思路递归四剑指平衡二叉树剑指平衡二叉树思路递归五相同的
思路:
递归二叉树的左子树,再递归二叉树的右子树,这样就可以把二叉树的左右子树都给弄成镜像二叉树;
再交换根的左右子树,那么整个树的镜像二叉树就出来了;
注意细节:当树为空就直接返回空树即可!
/** * 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* mirrorTree(TreeNode* root) { //递归结束条件,树为空,镜像也是空 if(root == NULL) return NULL; //来到这里书名树不为空 //递归左子树,再递归右子树 mirrorTree(root->left); mirrorTree(root->right); //交换根的左结点和右节点 swap(root->left,root->right); return root; }};
思路:
只要判断左子树和右子树是否为对称即可;
那么如何判断左子树和右子树是否对称呢?
构造一个新的函数,判断两颗树是否对称即可;
/** * 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* root1,TreeNode* root2) { //如果两棵树都是空,那么为真,对称 if(root1 == NULL && root2 == NULL ) return true; //如果任意一颗为空,另一个不为空,那么就不对称 if(root1 == NULL || root2 == NULL) return false; //两棵树的根结点相等的同时,也保证一个树的左子树和另一个树的右子树相等, //相反也是,那么就可以说是对称的两棵树 return root1->val == root2->val && _isSymmetric(root1->left,root2->right) && _isSymmetric(root1->right,root2->left); } //判断一棵树是否为对称的二叉树 bool isSymmetric(TreeNode* root) { if(root == NULL) return true; return _isSymmetric(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: int maxDepth(TreeNode* root) { if(root == NULL) return 0; if(root->left == NULL && root->right == NULL) return 1; int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return max(leftDepth,rightDepth) +1; }};
思路:
只要判断左子树是否为平衡树,右子树是否为平衡树,同时判断左右子树的高度差绝对值不超过一即可!
如何判断左右子树高度差不超过一?
只要写一个新函数,求出二叉树的深度,再求左右子树的高度差绝对值即可;
/** * 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: //求二叉树的深度 int maxDepth(TreeNode* root) { if(root == NULL) return 0; if(root->left == NULL && root->right == NULL) return 1; int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return max(leftDepth,rightDepth) +1; } //判断是否为平衡树 bool isBalanced(TreeNode* root) { if(root == NULL) return true ; return abs(maxDepth(root->left)-maxDepth(root->right)) <=1 && isBalanced(root->left) && isBalanced(root->right); }};
只要判断q树的左子树和p树的左子树相等和q树的右子树和p树的右子树都相等即可!
如何判断呢?递归判断;
/** * 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 isSameTree(TreeNode* p, TreeNode* q) { //空树一定是相等的树 if(p == NULL && q == NULL) return true; //任意一个为空,另一个不为空都不是相等的树 if(p == NULL || q == NULL) return false; //递归左子树和右子树,判断其对应结点是否为相等即可 return p->val == q->val && isSameTree(p->left,q->left) && isSameTree(p->right,q->right); }};
子树和二叉树相等,那么子树一定是二叉树的子树;
如果不相等,再递归判断子树是否为二叉树的左子树,或者递归判断子树是否为二叉树的右子树,只要满足一个,那么就说明子树一定是二叉树的子树了;
/** * 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 isSametree( TreeNode* root1, TreeNode* root2){ if(root1 == NULL && root2 == NULL ) return true; //只要有一个为空另一个不为空那么就不是相同的树 if(root1 == NULL || root2 == NULL) return false; return root1->val == root2->val && isSametree(root1->left,root2->left) && isSametree(root1->right,root2->right);} //判断是否为二叉树的子树 bool isSubtree(TreeNode* root, TreeNode* subRoot) { //如果root为空树,subRoot肯定不是它的子树 if(root == NULL) return false; //如何子树和树相同,那么一定是子树 if(isSametree(root,subRoot)) return true; //否子递归树的左子树判断和子树相等或者递归树的右子树和子树相等即可 return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot); }};
思路:
递归左子树和右子树判断是否为单值二叉树,同时要保证左子树的根和右子树的根是和二叉树相等的;
如何保证左子树的根和右子树的根是和二叉树相等?
我们只需要判断它的对立面,把对立面考虑出来就行:
假如二叉树树的左子树不为空,那么左子树的根和二叉树的根不相等,这就肯定不是单值二叉树;
假如二叉树树的右子树不为空,那么右子树的根和二叉树的根不相等,这就肯定不是单值二叉树;
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; *///判断根是否和左子树或者右子树相等,是就是单值二叉树bool isUnivalTree(struct TreeNode* root){ if(root == NULL) return true; //如果左子树的结点和根结点不相等就不是单值二叉树 //前提需要判断左子树存在,即不为空就表示存在 if(root->left && root->left->val !=root->val) { return false; } //如果右子树的结点和根结点不相等就不是单值二叉树 //前提需要判断右子树存在,即不为空就表示存在 if(root->right && root->right->val !=root->val) { return false; } //假如直接返回 true就会出错,因为你上面的代码只是保证了根和根的左右孩子相等 //但是没有保证,左右孩子的下面的子左右孩子是否相等呀 //return true; //错误返回方式 //正确的方式 //还需要继续判断左右子树下面的子左右子树的值是否为单值 return isUnivalTree(root->left) && isUnivalTree(root->right);}
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/123700.html
摘要:二叉树层序遍历每一层值分别存储到一个可能不同的人看的着重点不完全相同,我注意到的是以上三个。二叉树的层序遍历还是比较好搞的,根据数据结构的基础知识,只要我们借助一个队列,利用队列的先进先出的特性,就能够很好的进行层序遍历。 ...
摘要:重建二叉树详解题目描述原理分析大致思路细节阐述代码实现主函数递归函数参数区间的决定递归结束的条件总结题目描述原理分析大致思路下面讲解一下,前序遍历中序遍历如何确定一个唯一的二叉树。 ...
摘要:月下半旬攻略道题,目前已攻略题。目前简单难度攻略已经到题,所以后面会调整自己,在刷算法与数据结构的同时,攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题,目前已攻略 100 题。 一 目录 不折腾的前端,和咸鱼有什么区别...
摘要:微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容,进行补充,并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目录 不...
摘要:题目给定一个二叉树,返回其按层次遍历的节点值。例如给定二叉树返回其层次遍历结果题解我们数据结构的书上教的层序遍历就是利用一个队列不断的把左子树和右子树入队。 题目 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如:给定二叉树: [3,9,20,null,null,15,7], 3 / 9 20 / 15 ...
阅读 1101·2023-04-25 18:34
阅读 3215·2021-11-19 09:40
阅读 1471·2021-11-18 10:02
阅读 2617·2021-11-17 09:33
阅读 1307·2021-11-15 11:37
阅读 2721·2021-11-12 10:36
阅读 2575·2021-09-26 09:55
阅读 1841·2021-09-08 09:36