C语言从二叉树t中,查找距离*p最近的叶子结点
时间: 2024-05-08 22:21:30 浏览: 56
可以通过递归的方式遍历整个二叉树,同时记录当前节点到根节点的路径上的节点个数,找到距离*p最近的叶子节点。
具体实现如下:
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int findClosestLeaf(struct TreeNode* t, struct TreeNode* p) {
if (!t) return INT_MAX; // 递归到空节点,返回一个较大的值,表示不存在叶子节点
if (t == p && !t->left && !t->right) return 0; // 当前节点就是目标节点,并且当前节点是叶子节点,返回0
int left = findClosestLeaf(t->left, p); // 递归查找左子树
int right = findClosestLeaf(t->right, p); // 递归查找右子树
if (left <= right) { // 如果左子树离目标节点更近
if (t->left && !t->right) { // 如果左子树存在,右子树不存在,说明t的右子树到叶子节点的距离为INT_MAX
return left + 1; // 返回左子树到叶子节点的距离
} else { // 否则,t的左右子树都存在
int dist = findNearestLeaf(t->right, left + 2); // 递归查找t的右子树到叶子节点的距离
return dist <= right ? dist : right; // 返回左子树到叶子节点的距离和右子树到叶子节点的距离中的较小值
}
} else { // 如果右子树离目标节点更近
if (t->right && !t->left) { // 如果右子树存在,左子树不存在,说明t的左子树到叶子节点的距离为INT_MAX
return right + 1; // 返回右子树到叶子节点的距离
} else { // 否则,t的左右子树都存在
int dist = findNearestLeaf(t->left, right + 2); // 递归查找t的左子树到叶子节点的距离
return dist <= left ? dist : left; // 返回左子树到叶子节点的距离和右子树到叶子节点的距离中的较小值
}
}
}
```
该函数的时间复杂度为 $O(n)$,其中 $n$ 为二叉树的节点个数。