设计一个递归算法检查以二叉链表存储的两棵二叉树是否完全相同
时间: 2024-05-07 17:19:21 浏览: 41
可以使用递归算法来检查两棵二叉树是否相同。具体步骤如下:
1. 首先判断两棵二叉树的根节点是否相同,如果不同则返回 false。
2. 如果根节点相同,则递归地检查左子树和右子树是否相同。
3. 如果左子树和右子树都相同,则返回 true,否则返回 false。
下面是一个示例代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_same_tree(p: TreeNode, q: TreeNode) -> bool:
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
```
其中,p 和 q 分别为两棵二叉树的根节点。该函数返回一个布尔值,表示两棵二叉树是否相同。
相关问题
设计一个递归算法检查以二叉链表存储的两棵二叉树是否完全相同(C语言)
以下是递归算法实现:
```c
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;
}
if (p->val != q->val) {
return false;
}
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
```
该算法接收两个二叉树的根节点 `p` 和 `q`,如果 `p` 和 `q` 都为 `NULL`,则这两棵二叉树相同,返回 `true`。如果其中一个为 `NULL`,则这两棵二叉树不同,返回 `false`。如果两棵二叉树的根节点值不相等,则这两棵二叉树不同,返回 `false`。最后使用递归调用判断 `p` 和 `q` 的左子树和右子树是否相同,如果都相同则这两棵二叉树也相同,返回 `true`。
用C语言求二叉树高度 用二叉链表创建一棵二叉树并利用递归算法求它的高度。
C语言代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int tree_height(TreeNode* root) {
if (!root) {
return 0;
}
int left_height = tree_height(root->left);
int right_height = tree_height(root->right);
return (left_height > right_height ? left_height : right_height) + 1;
}
int main() {
// 创建一棵二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 5;
root->right->right->left = NULL;
root->right->right->right = NULL;
// 计算二叉树高度
int height = tree_height(root);
printf("二叉树的高度为:%d\n", height);
return 0;
}
```
在这个程序中,我们定义了一个`TreeNode`结构体表示二叉树节点,其中包含`val`表示节点的值,`left`和`right`分别表示左右子树指针。接着,我们定义了一个`tree_height`函数用于递归计算二叉树高度。在函数中,先判断当前节点是否为空,如果为空,则返回0;否则,分别递归求解左子树和右子树的高度,最后返回左右子树高度的较大值加1。
在`main`函数中,我们创建了一棵二叉树,并调用`tree_height`函数计算它的高度。最后,程序输出二叉树的高度。