leetcode543.二叉树的直径

迷南。 2023-07-13 08:21 10阅读 0赞

**题目描述：**

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

示例 :  
给定二叉树

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

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

测试用例：\[1,2,3,4,5\]

返回结果：3

**解决思路：**

一开始没明白为什么把这个最长路径叫做二叉树的直径，觉得二叉树的直径应该是二叉树形状中最粗的那一部分。后来把二叉树看作普通的图，最长的路径不就是最宽的那一块嘛，原来直径的说法是这么理解的。

最初的想法是以根节点为轴，左子树的高度加右子树的高度就是最长的路径了。但事实上最长路径不一定会经过根节点，比如:

/        \\

2          3

/    \\

4       5

/     \\   /

6      7 8

64258就是最长的路径4，也不经过根节点。所以立刻想到的是求出属于每一个节点的最长路径，然后在这些路径里找出最大值，就是整棵树的直径了。

每一个节点的最长路径就是它的左子树高度 + 它的右子树高度。（所求的是路径上的节点个数减一，这和左子树高度加右子树高度的值相同，这算是一个小规律）

求树的高度，递归。

在遍历每一个节点的时候，既能求该节点的高度，又能求以该节点为轴的长度。

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    
    int dia = 0;
    
    int depth(struct TreeNode* root){
        if(root == NULL){
           return 0;
        }
        int l = depth(root->left);
        int r = depth(root->right);
        dia = fmax(dia, l + r);
        return fmax(l, r) + 1;    
    }
    
    int diameterOfBinaryTree(struct TreeNode* root){
        dia = 0;
        depth(root);
        return dia;
    }