【leetcode】543. 二叉树的直径（diameter-of-binary-tree）（dfs）[简单]

链接

https://leetcode-cn.com/problems/diameter-of-binary-tree/

耗时

解题：12 min
题解：18 min

题意

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

思路

这是一个经典问题，可以两次 bfs 解决，但这题是二叉树，我突然有了一个非常简单的写法，虽然复杂度很高。
我发现：二叉树过根节点的直径是 根节点的 左子树的高度+右子树的高度。
所以，计算所有节点左右子树的高度和，其中的最大值即是树的直径。

优化可以复制当前树，复制的树节点存储每个节点的高度，一次 dfs 即可得到所有子树的高度，之后无需重复计算，时间复杂度 O(n)。

时间复杂度： O ( n 2 ) O(n^2) O(n2)

AC代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int dfs(TreeNode* root) {
        if(root == NULL) return 0;
        return max(dfs(root->left), dfs(root->right)) + 1;
    }
    
    int diameterOfBinaryTree(TreeNode* root) {
        if(root == NULL) return 0;
        int leftHeight = dfs(root->left);
        int rightHeight = dfs(root->right);
        return max(leftHeight+rightHeight, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
    }
};