力扣---二叉树OJ题(多种题型二叉树)
发布时间：2023-06-28 15:00:26
一、剑指 Offer 55 - I. 二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。
1.1 链接：
剑指 Offer 55 - I. 二叉树的深度
1.2 代码一：
int maxDepth(struct TreeNode* root) { if(root==NULL) return 0; int leftTree=maxDepth(root->left); int rightTree=maxDepth(root->right); return leftTree>rightTree?leftTree+1:rightTree+1; }
1.3 代码二：
这种代码是正确的但是在力扣上是不能通过的时间太长具体分析可以看【数据结构】—几分钟简单几步学会手撕链式二叉树(中)中求二叉树高度部分
int maxDepth(struct TreeNode* root) { if (root == NULL) return 0; return maxDepth(root->left) > maxDepth(root->right) ? maxDepth(root->left) + 1 : maxDepth(root->right) + 1; }
1.4 流程图：
二、100. 相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
2.1 链接：
2.2 思路：
采用前序,先比较 根 然后 左子树 右子树，而结束条件就是为空树或者不相等
2.3 代码：
bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if(p==NULL&&q==NULL)//两者都为空树则表示相同 return true; if(p==NULL||q==NULL)//有一个不为空则不同 return false; if(p->val!=q->val)//数值不同则不同 return false; return isSameTree(p->left, q->left)&&isSameTree(p->right, q->right);//采用逻辑与当左树不相同时，就没必要比较右树 }
2.4 流程图：
三、965. 单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
3.1 链接：
965. 单值二叉树
3.2 思路：
采用传递性：ab bc <> ac,然后通过对比根节点和左子树，左子树，右子树来判断值是否相同
3.3 代码：
bool isUnivalTree(struct TreeNode* root) { if(root==NULL) return true; if(root->left!=NULL&&root->left->val!=root->val) //左子树不为空且左子树的值和根值不同 return false; if(root->right!=NULL&&root->right->val!=root->val) //右子树不为空且右子树的值和根值不同 return false; return isUnivalTree(root->left)&&isUnivalTree(root->right); }
3.4 流程图：
四、101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
4.1 链接：
101. 对称二叉树
4.2 思路：
因为是轴对称，所以要比较左子树的值和右子树的值相同。
4.3 代码：
bool _isSymmetric(struct TreeNode* leftRoot,struct TreeNode* rightRoot) { if(leftRoot==NULL&&rightRoot==NULL) return true; if(leftRoot==NULL||rightRoot==NULL) return false; if(leftRoot->val!=rightRoot->val) return false; return _isSymmetric(leftRoot->left,rightRoot->right) &&_isSymmetric(leftRoot->right,rightRoot->left); } bool isSymmetric(struct TreeNode* root) //这个函数是题给出的所以不能修改但不符合所以使用返回值 { //因为题目给出根不为空所以只需要比较左右子树就可以了 return _isSymmetric(root->left,root->right); }
4.4 流程图：
五、144. 二叉树的前序遍历
5.1 链接：
5.2 代码(错误代码)：
下面这种写法是不能通过的，因为每次调用i++,都是各是各的造成了干扰具体可以看流程图
int TreeSize(struct TreeNode* root) { return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1; } void _preorderTraversal(struct TreeNode* root, int* a,int i) { if(root==NULL) return; a[i++]=root->val; _preorderTraversal(root->left,a,i); _preorderTraversal(root->right,a,i); } int* preorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize=TreeSize(root); int* a=(int*)malloc(sizeof(int)*(*returnSize)); int i=0; _preorderTraversal(root,a,i); return a; }
5.3 流程图：
5.4 两种解决方法：
5.4.1第一种：给i传地址
代码：
int TreeSize(struct TreeNode* root) { return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1; } void _preorderTraversal(struct TreeNode* root, int* a,int* pi) { if(root==NULL) return; a[(*pi)++]=root->val; _preorderTraversal(root->left,a,pi); _preorderTraversal(root->right,a,pi); } int* preorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize=TreeSize(root); int* a=(int*)malloc(sizeof(int)*(*returnSize)); int i=0; _preorderTraversal(root,a,&i); return a; }
5.4.2第而种：全局变量
代码：
一点注意：要在一次调用后置零，不然下次调用时就会出现i在上一次的基础值上接着走而数组就不是从0开始的
int TreeSize(struct TreeNode* root) { return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1; } int i=0; void _preorderTraversal(struct TreeNode* root, int* a) { if(root==NULL) return; a[i++]=root->val; _preorderTraversal(root->left,a); _preorderTraversal(root->right,a); } int* preorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize=TreeSize(root); int* a=(int*)malloc(sizeof(int)*(*returnSize)); i=0;//注意这里 _preorderTraversal(root,a); return a; }
总结
Ending,今天的链式二叉树的内容就到此结束啦~，如果后续想了解更多，就请关注我吧。
