二叉树相关算法实现：判断子树与单值二叉树

目录

一、判断一棵树是否为另一棵树的子树 

（一）核心思路 

（二）代码实现 

 （三）注意要点 

二、判断一棵树是否为单值二叉树 

（一）核心思路 

（二）代码实现 

（三）注意要点 

---

在二叉树的算法学习中，判断一棵树是否为另一棵树的子树，以及判断一棵树是否为单值二叉树是常见的问题。本文将结合具体的代码实现，深入剖析这两个问题的解决思路及注意要点。
 

一、判断一棵树是否为另一棵树的子树
 

（一）核心思路
 

要判断  root  树中是否包含  subRoot  树作为子树，可采用递归的方法。首先处理边界情况，若  subRoot  为空，说明空树是任何树的子树，返回  true ；若  root  为空且  subRoot  不为空，则  subRoot  不可能是  root  的子树，返回  false 。然后比较两棵树的根节点值，若不相等，在  root  的左子树和右子树中分别递归查找  subRoot ；若相等，进一步判断以该节点为根的子树是否与  subRoot  完全相同，可借助辅助函数  isSameTree  来实现。
 

（二）代码实现
 

c/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/// 辅助函数，判断两棵树是否完全相同
bool isSameTree(struct TreeNode* p, struct 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);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {if (subRoot == NULL) {return true;}if (root == NULL && subRoot!= NULL) {return false;}if (root->val!= subRoot->val) {// 用 || 分别在左右子树中查找return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);} else {// 判断以当前节点为根的子树和subRoot是否相同return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);}
}

 
（三）注意要点
 

1. 边界条件处理：在  isSubtree  和  isSameTree  函数中，都要先对空指针情况进行判断，这是递归算法的基础，避免出现空指针引用错误。
 
2. 递归逻辑：在  isSubtree  中，当根节点值不相等时，使用逻辑或  ||  分别在左右子树中查找；当根节点值相等时，要同时考虑当前子树是否相同以及继续在左右子树中查找的情况。 isSameTree  中，只有当当前节点值相等且左右子树都相同时，两棵树才相同。
 

二、判断一棵树是否为单值二叉树
 

（一）核心思路
 

单值二叉树是指树中每个节点的值都相同。判断时，可采用递归的方式。先处理边界情况，若根节点为空，返回  true 。然后检查根节点的左子节点和右子节点（若存在）的值是否与根节点值相同，若有不相同的，返回  false 。最后递归检查左子树和右子树是否也满足单值二叉树的条件。
 

（二）代码实现
 

c/*** 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;}return isUniValTree(root->left) && isUniValTree(root->right);
}

 

（三）注意要点
 

1. 节点存在性判断：在检查左右子节点值时，要先判断子节点是否存在，避免空指针引用。
 
2. 递归终止条件：当遇到空节点时，作为递归的终止条件之一，返回  true ，因为空树可以看作是满足单值条件的。
 
通过对这两个二叉树相关算法的实现与分析，我们可以更深入地理解递归在二叉树问题中的应用，以及在处理二叉树结构时边界条件和逻辑判断的重要性。