543. 二叉树的直径
题目描述
给你一棵二叉树的根节点,返回该树的 直径 。
解题
要计算二叉树的直径,可以使用深度优先搜索(DFS)来找到最长路径。二叉树的直径是任意两个节点之间的最长路径长度,这条路径可能经过根节点,也可能不经过根节点。
具体实现方法是:
- 使用一个辅助函数来计算每个节点的深度。
- 在计算深度的过程中,更新直径的值。
- 递归计算左右子树的深度,然后通过更新直径来获取最长路径。
具体 Swift 代码实现 as follows:
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init() { self.val = 0; self.left = nil; self.right = nil; }
* public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
* public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
* self.val = val
* self.left = left
* self.right = right
* }
* }
*/
class Solution {
func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
var diameter = 0
func depth(_ node: TreeNode?) -> Int {
guard let node = node else {
return 0
}
let leftDepth = depth(node.left)
let rightDepth = depth(node.right)
// 更新直径,取当前直径和左子树深度+右子树深度的最大值
diameter = max(diameter, leftDepth + rightDepth)
// 返回当前节点的深度
return max(leftDepth, rightDepth) + 1
}
depth(root)
return diameter
}
}
解释
diameterOfBinaryTree
方法:初始化diameter
变量并定义depth
辅助函数。depth
辅助函数:- 如果节点为
nil
,返回深度为 0。 - 递归计算左右子树的深度。
- 更新
diameter
,它是左子树深度和右子树深度之和的最大值。 - 返回当前节点的深度,即左右子树深度的最大值加 1。
- 如果节点为
- 计算结果:调用
depth
方法从根节点开始计算,并返回最终的diameter
值。
这样,通过递归地计算每个节点的深度,同时更新全局的直径变量,最终可以得到二叉树的直径。