第12题 力扣LeetCode 热题 HOT 100(543. 二叉树的直径)_力扣hot100在哪里

第12题 力扣LeetCode 热题 HOT 100(543. 二叉树的直径)

题目

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    
1
2
3
4
5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

**注意：**两结点之间的路径长度是以它们之间边的数目表示。

题解

题意为求二叉树中两个节点之间边个数的最大值。

分析，因为是求直径，一颗树中任意两个节点的直径，是从最近父节点中练成一条线。

一颗节点的最长直径，即为该节点的左节点最长深度加右节点最长深度加上该节点自身（和为总节点个数），边数需要减去一。

维护一个sum值，每个节点都调用该函数。若有更大值出现，更新sum

/**
 * 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 sum = 0;
    let findDeepth = function(root){
        if(!root) return 0;
        else {
            let left = 0, right =0;
            left = findDeepth(root.left);
            right = findDeepth(root.right);
            if(left+right+1>sum ) sum = left+right+1;
            return left>right? left+1: right+1;
        }
    }
    findDeepth(root);
    return sum-1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27