543. Diameter of Binary Tree

Leetcode link

题目简介

/**
 * @param {TreeNode} root
 * @return {number}
 */

题目给我们一个二叉树的根节点 root

要求我们计算树中最远的两个节点的距离是多少（节点的距离由节点之间的连接数量决定）

解题思路

题目的要求翻译：我们需要找到二叉树的一个节点，这个节点的左右子树高度加起来最高

要求左右子树的高度，我们需要用到 dfs 的思路

由于我们需要找到左右子树高度和最高的节点，我们需要一个变量 maxDiameter 来记录当前左右子树高度之和的最高值

我们在 dfs 回溯的时候要做两件事：

1. 比较 maxDiameter 与 leftHeight + rightHeight 使用其最大值更新 maxDiameter（leftHeight 与 rightHeight 分别代表当前节点的左右子树高度）
2. 返回 max(leftHeight, rightHeight) + 1 用于给当前节点父节点提供判断子树高度的依据

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    let maxDiameter = 0

    const dfs = (node) => {
        if(!node) {
            return 0
        }

        const leftHeight = dfs(node.left)
        const rightHeight = dfs(node.right)

        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight)    
        return Math.max(leftHeight, rightHeight) + 1
    }

    dfs(root)
    return maxDiameter
};