创建二叉树并可得到二叉树中任意两个结点的距离
时间: 2024-06-19 20:04:00 浏览: 16
要创建二叉树,可以使用结构体来定义二叉树结点,结构体中包含指向左右子树的指针,如下所示:
```
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
```
接着可以使用递归的方法创建二叉树,每次读入一个结点的值,如果值为0,则表示该结点为空;否则新建一个结点,并递归创建左右子树。具体代码如下:
```
struct TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == 0) {
return NULL;
}
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = createTree();
node->right = createTree();
return node;
}
```
关于求任意两个结点的距离,可以转化为求它们的最近公共祖先节点,并计算出到该祖先节点的距离。可以使用后序遍历的方法求解。对于每个节点,先递归处理其左右子树,得到它们的最近公共祖先节点和距离,然后根据当前节点的左右子树情况计算出当前节点的最近公共祖先节点和距离,并返回给上一级调用。具体代码如下:
```
struct Result {
struct TreeNode* ancestor; // 最近公共祖先
int distance; // 距离
};
struct Result postorder(struct TreeNode* root, int p, int q) {
if (root == NULL) {
return (struct Result){NULL, -1};
}
struct Result left = postorder(root->left, p, q);
struct Result right = postorder(root->right, p, q);
if (left.ancestor != NULL && left.ancestor != NULL) { // p和q分别在左右子树中
return (struct Result){root, left.distance + right.distance + 2};
} else if (root->val == p || root->val == q) { // 当前节点是p或q中的一个
if (left.ancestor != NULL || right.ancestor != NULL) { // 另一个在子树中
return (struct Result){root, left.distance + right.distance + 2};
} else { // 另一个不在子树中
return (struct Result){root, 0};
}
} else { // p和q都在同一子树中
if (left.ancestor != NULL) {
return (struct Result){left.ancestor, left.distance + 1};
} else {
return (struct Result){right.ancestor, right.distance + 1};
}
}
}
int distance(struct TreeNode* root, int p, int q) {
struct Result result = postorder(root, p, q);
return result.distance;
}
```
注意,在使用完二叉树后需要释放内存,可以使用递归的方法进行释放,具体代码如下:
```
void freeTree(struct TreeNode* root) {
if (root == NULL) {
return;
}
freeTree(root->left);
freeTree(root->right);
free(root);
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)