543. 二叉树的直径

题目描述

给你一棵二叉树的根节点，返回该树的 直径 。

解题

要计算二叉树的直径，可以使用深度优先搜索（DFS）来找到最长路径。二叉树的直径是任意两个节点之间的最长路径长度，这条路径可能经过根节点，也可能不经过根节点。

具体实现方法是：

1. 使用一个辅助函数来计算每个节点的深度。
2. 在计算深度的过程中，更新直径的值。
3. 递归计算左右子树的深度，然后通过更新直径来获取最长路径。

具体 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
    }
}

解释

1. diameterOfBinaryTree 方法：初始化 diameter 变量并定义 depth 辅助函数。
2. depth 辅助函数：
   • 如果节点为 nil，返回深度为 0。
   • 递归计算左右子树的深度。
   • 更新 diameter，它是左子树深度和右子树深度之和的最大值。
   • 返回当前节点的深度，即左右子树深度的最大值加 1。
3. 计算结果：调用 depth 方法从根节点开始计算，并返回最终的 diameter 值。

这样，通过递归地计算每个节点的深度，同时更新全局的直径变量，最终可以得到二叉树的直径。