华为od机试 - 最佳植树距离
时间: 2023-10-29 12:02:48 浏览: 99
华为OD机试 - 最佳植树距离
题目要求:给定一个二叉树(不一定是完全二叉树),计算二叉树中每个节点到离它最近的另一个节点的最大距离。
解题思路:首先,我们可以通过递归的方式遍历整棵二叉树,对于每个节点,计算它到左子树最远节点的距离,再计算它到右子树最远节点的距离。然后,比较这两个距离,取其中较大的一个,再加上1(表示当前节点到其父节点的距离),就得到了当前节点到离它最近的另一个节点的最大距离。
代码实现(Python):
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDistance(root):
if not root:
return 0
leftMax = maxDistance(root.left)
rightMax = maxDistance(root.right)
return max(leftMax, rightMax) + 1
# 测试
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
print(maxDistance(root)) # 输出3,表示节点6到离它最近的另一个节点的最大距离是3
```
以上代码可以计算出二叉树中每个节点到离它最近的另一个节点的最大距离。
相关推荐
![html](https://img-home.csdnimg.cn/images/20210720083451.png)
![html](https://img-home.csdnimg.cn/images/20210720083451.png)
![html](https://img-home.csdnimg.cn/images/20210720083451.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)