二叉树经典题题解网站首页 技术杂谈

二叉树经典题题解

蛋超饭不要加蛋 2023-06-04 04:00:02

简介二叉树经典题题解

🍅1.单值二叉树 🍅

🍅1.单值二叉树🍅

题目OJ链接力扣

题目描述：

思路：

采用递归的思想，判断当前节点是否与左右孩子相等，不相等则返回false，相等则继续递归左右子树进行判断，并将左右子树判断的结果相&&并返回，递归到空节点说明之前都没有返回false，即前面的子树都返回真，所以递归到空节点则返回真

代码：

bool isUnivalTree(struct TreeNode* root){
if(root==NULL)//递归到空节点则返回真
return true;
if(root->left&&root->val!=root->left->val)//根节点与左孩子比较
return false;
if(root->right&&root->val!=root->right->val)//根节点与右孩子比较
return false;
//递归左右子树并将两个节点相与返回
return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

🍉2.相同的树🍉

题目链接力扣

题目描述：

思路：

利用递归的思想，先判断当前两个树根节点是否相同，然后再分别递归两个树当前节点的左孩子和右孩子进行比较，如果过程中有不相等的节点例如则返回false，或者一个树的节点存在而另一个树的节点不存在则返回false，直到递归到两个树的空节点说明之前的节点都相等则返回true

代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p==NULL&&q==NULL)//递归到两个树的空节点则返回真
return true;
if(p==NULL||q==NULL)//一棵树的节点存在而另一颗的节点不存在则返回false
return false;
if(p->val!=q->val)//节点的值不相等则返回fasle
return false;
//分别递归两个树的左右子树，并将结果相与并返回
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

🍊3.对称二叉树🍊

题目链接力扣

题目描述：

思路：

复用第二题相同的树的代码，相同的树题目中是将一颗树的根节点与另一颗的根节点比较，然后再分别比较左孩子和右孩子，这题我们可以将比较反过来，即一个树节点的左孩子和另一个数节点的右孩子进行比较，一个树节点的右孩子和另一个树节点的右孩子进行比较

代码：

bool _isSymmetric(struct TreeNode* root1,struct TreeNode* root2)
{
if(root1==NULL&&root2==NULL)//递归到两个树的空节点则为真
return true;
if(root1==NULL||root2==NULL)//有一个树的节点存在而另一个树的节点不存在则返回false
return false;
if(root1->val!=root2->val)//节点的值不相等则返回false
return false;
//分别递归两个树的左右子树，左孩子节点与右孩子比较，右孩子节点与左孩子比较
return _isSymmetric(root1->left,root2->right)&&_isSymmetric(root1->right,root2->left);
}
bool isSymmetric(struct TreeNode* root){
return _isSymmetric(root->left,root->right);
}

🍎4.另一颗树的子树🍎

题目链接力扣

题目描述：

思路：

利用递归的思想，判断两棵树是否都为空树，都为空树则返回真，再判断两颗子树是否有一个为空有一个不为空，如果是说明两个树不同则返回false。先判断整颗树是否与该子树相同，再递归判断左子树是否与该子树相同，最后判断递归右子树是否与该子树相同，如果左右子树都不与该子树，则返回false

代码：

//相同的树代码
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);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL&&subRoot==NULL)//两个树都为空则返回真
return true;
if(root==NULL||subRoot==NULL)//两个树有一个为空有一个不为空则返回false
return false;
if(isSameTree(root,subRoot))//判断整个树是否与该子树相同
return true;
if(isSubtree(root->left,subRoot))//再判断左子树是否与该子树相同
return true;
if(isSubtree(root->right,subRoot))//最后判断左子树是否与该子树相同
return true;
//左右子树都不和该子树相同则返回false
return false;
}

🍏5.翻转二叉树🍏

题目链接力扣

题目描述：

思路：

利用递归的思想，首先判断当前树是否为空树，为空树则返回空，接着进行翻转，首先将当前根节点的左右孩子进行交换，由于节点之间是进行指针链接的，故交换了左右孩子即交换了左右子树，然后递归交换左子树的左右孩子，最后递归交换右子树的左右孩子，直到递归到空节点则结束

代码：

void _invertTree(struct TreeNode* root)
{
if(root==NULL)//递归到空节点则结束
return;
//左右孩子进行交换
struct TreeNode* tmp=root->left;
root->left=root->right;
root->right=tmp;
递归左右子树
_invertTree(root->left);
_invertTree(root->right);
}
struct TreeNode* invertTree(struct TreeNode* root){
if(root==NULL)
return NULL;
_invertTree(root);
return root;
}

🍑 6.平衡二叉树🍑

题目链接力扣

题目描述：

思路：

先写出求一棵树的高度的函数（见上一篇文章），再判断整棵树的左右子树高度差的绝对值是否小于1，如果左子树存在则递归左子树，判断左子树的左右子树高度差的绝对值是否小于1，然后如果右子树存在则递归左子树，判断右子树的左右子树高度差的绝对值是否小于1，如果左子树的左右子树高度差和右子树的左右子树高度差绝对值都小于1则返回真，或者直到递归到空节点或者叶子结点则说明之前的递归过程没有返回false即平衡二叉树的条件，此时返回true

代码：

//求树的高度的函数
int HeightTree(struct TreeNode* root)
{
if(root==NULL)
return 0;
if(root->left==NULL&&root->right==NULL)
return 1;
int left=HeightTree(root->left);
int right=HeightTree(root->right);
return left>right? left+1:right+1;
}
bool isBalanced(struct TreeNode* root){
if(root==NULL)//递归到空节点则返回真
return true;
if(root->left==NULL&&root->right==NULL)//递归到叶子节点则函数真
return true;
if(abs(HeightTree(root->left)-HeightTree(root->right))>1)//判断当前左右子树高度差绝对值
return false;
if(root->left)//左子树存在则递归左子树
{
if(isBalanced(root->left)==false)
return false;
}
if(root->right)//右子树存在则递归右子树
{
if(isBalanced(root->right)==false)
return false;
}
//左右子树的左右子树高度差绝对值都小于1则返回真
return true;
}