当前位置：首页 > news >正文

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

news 来源：原创 2025/7/22 3:27:26

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

（一）核心思路

（二）代码实现

（三）注意要点

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

（一）核心思路

（二）代码实现

（三）注意要点

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

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

（一）核心思路

要判断 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 ，因为空树可以看作是满足单值条件的。

通过对这两个二叉树相关算法的实现与分析，我们可以更深入地理解递归在二叉树问题中的应用，以及在处理二叉树结构时边界条件和逻辑判断的重要性。

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

（一）核心思路

（二）代码实现

（三）注意要点

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

（一）核心思路

（二）代码实现

（三）注意要点

相关文章：