2021-01-03 | 543. 二叉树的直径

小鱼儿 2023-01-01 14:49 116阅读 0赞

### 1. 题目描述 ###

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

示例 :  
给定二叉树

1
           / \
          2   3
         / \     
        4   5

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

### 2. 解题思路 ###

遇到二叉树的问题，我们在遍历时通常是采用深度优先遍历和广度优先遍历，这里需要求直径，我们就使用到了深度优先遍历。

从根节点进行遍历，在遍历到每个节点的时候，将其左右子树的最大深度加在一起，与结果res对比，并将最大的值赋值给热搜，这样使res一直保持是最大的值。

最后返回res即可。

**复杂度分析：**

*  时间复杂度：O(n)，其中n为二叉树的节点数，这里需要遍历整棵二叉树，所以时间复杂度为O(n)。
 *  空间复杂度：O(h)，其中h是二叉树的最大深度，是一个常数变量。

### 3. 代码实现 ###

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
    /** * @param {TreeNode} root * @return {number} */
    var diameterOfBinaryTree = function(root) {  
        let res = 0
    
        function depth(rootNode){ 
            if(!rootNode) return 0
    
            let l = depth(rootNode.left)  // l为左子树的深度
            let r = depth(rootNode.right) // r为右子树的深度
    
            res = Math.max(res, l + r)    // 计算最大直径l+r，更新res，能保持其一直是最大值
            return Math.max(l ,r) + 1     // 返回以该节点为根的子树的深度
        }
        depth(root)
        return res
    };

### 4. 提交结果 ###

![在这里插入图片描述][20210103144126294.png]

[20210103144126294.png]: /images/20221120/3588928d01fe466abedca86c548da639.png?