Data Structure--二叉树例题解析(1)--单值二叉树--翻转二叉树--相同的树--另一个树的子树--对称二叉树--平衡二叉树

Love The Way You Lie 2022-10-31 13:47 146阅读 0赞

### 二叉树例题解析 ###

*   *  1.单值二叉树
     *  2.翻转二叉树
     *  3.相同的树
     *  4.另一个树的子树
     *  5.对称二叉树
     *  6.平衡二叉树

## 1.单值二叉树 ##

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]

bool _isUnivalTree(struct TreeNode* root, int val){ 
    
    	if (root){ 		//存在时
    
    		return root->val == val		//等于同一个值
    			&& _isUnivalTree(root->left, val)	//递归看左节点的
    			&& _isUnivalTree(root->right, val);	//递归看右节点的
    	}
    	return true;	//如果上面完成了,返回真
    }
    
    bool isUnivalTree(struct TreeNode* root){ 
    	
    	if (root == NULL)
    		return true;	//为空也是真
    		
    	return _isUnivalTree(root, root->val);		//调用
    }

## 2.翻转二叉树 ##

将一个二叉树进行翻转,形成其镜像的样子  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]

struct TreeNode* invertTree(struct TreeNode* root){ 
    
    	if (root == NULL)
    		return NULL;		//判空
    		
    	//交换左右子树
    	struct TreeNode* tmp = root->left;		//直接对左右的子树进行交换
    	root->left = root->right;
    	root->right = tmp;
    
    	invertTree(root->left);		//递归调用
    	invertTree(root->right);	
    	return root;
    }

**注意,上面的交换只能交换这个节点的两个子树,不能使整个进行交换,所以才需要不停地递归,对每一个节点的子树进行交换**

## 3.相同的树 ##

比较是不是一样的二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]

bool isSameTree(struct TreeNode* p, struct TreeNode* q){ 
    
    	if (p == NULL&&q == NULL)	//判空
    		return true;
    		
    	//没有同时到达NULL
    	if (p == NULL || q == NULL)	//判空
    		return false;
    		
    	return p->val == q->val			//两个树的同一位置节点进行比较
    		&& isSameTree(p->left, p->left)		//左边递归
    		&& isSameTree(q->left, q->left);	//右边递归
    }

同样,需要挨个进行递归

## 4.另一个树的子树 ##

求二叉树里面的一个子树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]

bool isSameTree(struct TreeNode* p, struct TreeNode* q){ 
    
    	if (p == NULL&&q == NULL)
    		return true;
    	//没有同时到达NULL
    	if (p == NULL || q == NULL)
    		return false;
    		
    	return p->val == q->val				
    		&&isSameTree(p->left, q->left)
    		&& isSameTree(p->right, q->right);
    }
    bool isSubtree(struct TreeNode* s, struct TreeNode* t){ 
    
    	if (t == NULL)
    		return true;
    	if (s == NULL)
    		return false;
    		
    	return isSameTree(s, t)		//函数调用取出来对应的节点
    		|| isSubtree(s->left, t)	//递归调用
    		|| isSubtree(s->right, t);
    }

多根据代码进行理解

## 5.对称二叉树 ##

看是否对称  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 4]

bool _isSym(struct TreeNode* left, struct TreeNode* right){ 
    
    	if (left == NULL&&right == NULL)		//都为空也对称
    		return true;
    	if (left == NULL || right == NULL)		//或操作
    		return false;
    		
    	return left->val == right->val			//看对应位置是否相等,一左一右
    		&& _isSym(left->left, right->right)		//与操作
    		&& _isSym(left->right, right->left);
    }
    
    bool isSymmetric(struct TreeNode* root){ 
    	if (root == NULL)		//为空也对称
    		return true;
    		
    	return _isSym(root->left, root->right);		//函数调用
    }

## 6.平衡二叉树 ##

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 5]

int getHeight(struct TreeNode* root){ 
    
    	if (root){ 		//如果存在
    
    		int left = getHeight(root->left);		//利用整形将左右的高度赋予
    		int right = getHeight(root->right);
    		return left>right ? left + 1 : right + 1;	//如果左大,则左+1,不然则右+1
    	}
    	return 0;
    }
    
    bool isBalanced(struct TreeNode* root){ 
    	
    	if (root == NULL)		//为空也平衡
    		return true;
    		
    	int left = getHeight(root->left);
    	int right = getHeight(root->right);
    
    	//当前节点的左右子树插差<2
    	return abs(left - right)<2
    		&& isBalanced(root->left)
    		&& isBalanced(root->right);		//与操作并递归,多画图进行说明
    }

这里主要运用的是递归的方法,只要掌握递归以及代码内部运行的流图就很简单了,多敲代码!!!一起加油!!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/29b50d4d22e6439eb818aab89eeeb2f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221024/b76f2fd0c0a449888bc8b31e3725ea34.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]: /images/20221024/ed0f7091cfa744969cdd4a39d0ba1d40.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]: /images/20221024/6fd39be9b70b4aa88ec00766889f114b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 4]: /images/20221024/3f6825298add4e65b914fb9cfe58746e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 5]: /images/20221024/298a266997e04c3785b1c7d41e5f0f29.png