[已解决]二叉树中相距最远的两个节点间的距离

好故事慢慢来

给定一个二叉树，求二叉树中相距最远的两个节点的距离，麻烦给出以下完整代码，和思路，给个c语言的，谢谢大佬

最佳答案

月排行榜 / 总排行榜

isdkz

2023-6-16 13:46:35

这种问题被称为求二叉树的直径，二叉树的直径被定义为树中任意两节点之间最长路径的长度。此问题可以通过深度优先搜索 (DFS) 的方法解决。

我们可以遍历每个节点，对于每个节点，我们计算左右子树的深度，然后相加。其中的最大值就是我们要找的最长路径。

以下是Python的代码实现：

1. class TreeNode:
   
2.     def __init__(self, x):
   
3.         self.val = x
   
4.         self.left = None
   
5.         self.right = None
   
6. 
   
7. class Solution:
   
8.     def __init__(self):
   
9.         self.max_diameter = 0
   
10. 
    
11.     def diameterOfBinaryTree(self, root: TreeNode) -> int:
    
12.         self.depth(root)
    
13.         return self.max_diameter
    
14. 
    
15.     def depth(self, node):
    
16.         if node is None:
    
17.             return 0
    
18.         # 分别计算左右子树的深度
    
19.         left_depth = self.depth(node.left)
    
20.         right_depth = self.depth(node.right)
    
21.         # 更新最大直径
    
22.         self.max_diameter = max(self.max_diameter, left_depth + right_depth)
    
23.         # 返回节点深度
    
24.         return max(left_depth, right_depth) + 1
    

复制代码

我们定义一个全局变量  max_diameter  来保存当前最大直径，然后通过递归的方式求出每个节点的左右子树的深度，这个深度就是从当前节点到其最远的叶子节点的最长路径。因为直径可能经过根节点，所以每次计算深度时，都要更新  max_diameter 。最后，递归遍历整个树， max_diameter  就是最长路径的长度。

跳转到最佳答案楼层

isdkz

这种问题被称为求二叉树的直径，二叉树的直径被定义为树中任意两节点之间最长路径的长度。此问题可以通过深度优先搜索 (DFS) 的方法解决。

我们可以遍历每个节点，对于每个节点，我们计算左右子树的深度，然后相加。其中的最大值就是我们要找的最长路径。

以下是Python的代码实现：

1. class TreeNode:
   
2.     def __init__(self, x):
   
3.         self.val = x
   
4.         self.left = None
   
5.         self.right = None
   
6. 
   
7. class Solution:
   
8.     def __init__(self):
   
9.         self.max_diameter = 0
   
10. 
    
11.     def diameterOfBinaryTree(self, root: TreeNode) -> int:
    
12.         self.depth(root)
    
13.         return self.max_diameter
    
14. 
    
15.     def depth(self, node):
    
16.         if node is None:
    
17.             return 0
    
18.         # 分别计算左右子树的深度
    
19.         left_depth = self.depth(node.left)
    
20.         right_depth = self.depth(node.right)
    
21.         # 更新最大直径
    
22.         self.max_diameter = max(self.max_diameter, left_depth + right_depth)
    
23.         # 返回节点深度
    
24.         return max(left_depth, right_depth) + 1
    

复制代码

我们定义一个全局变量  max_diameter  来保存当前最大直径，然后通过递归的方式求出每个节点的左右子树的深度，这个深度就是从当前节点到其最远的叶子节点的最长路径。因为直径可能经过根节点，所以每次计算深度时，都要更新  max_diameter 。最后，递归遍历整个树， max_diameter  就是最长路径的长度。

好故事慢慢来

isdkz 发表于 2023-6-16 13:46
这种问题被称为求二叉树的直径，二叉树的直径被定义为树中任意两节点之间最长路径的长度。此问题可以通过深 ...

能给一个c语言的代码吗，没学过py，谢谢