Leetcode543. 二叉树的直径

题目描述

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

示例 :
给定二叉树

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

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

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

解题思路

这道题可以借鉴Leetcode124. 二叉树中的最大路径和中的思路，用相似的DFS搜索方法来求解。

这道题相比较最大路径和，要简单了很多。我们需要求解左子树和右子树的层数，并且用左子树与右子树的和去更新路径长度最大值maxPath的值，而返回左子树与右子树层数的最大值加上根节点（1）的值。

具体步骤如下：

  • 如果结点为空节点，返回为0；
  • 用left和right来标记左子树和右子树的层数。然后用left+right的值去更新路径长度最大值maxPath的值；
  • 计算max(left,right)+1的值，将其作为返回值返回。max(left,right)+1表示的意思就是当前结点可以返回的最大值，它的值为左子树与右子树层数的最大值加上根节点（1）。

时间复杂度：O(N)O(N)，其中 NN为二叉树的节点数

空间复杂度：O(Height)O(Height)，其中 $Height $为二叉树的高度

根据算法写出的示例代码如下。

示例代码

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
28
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

int dfs(TreeNode* root,int &maxPath)
{
    if(!root) return 0;
    int left=dfs(root->left,maxPath);
    int right=dfs(root->right,maxPath);
    if(left+right>maxPath)
    {
        maxPath=left+right;
    }
    return max(left,right)+1;
}

int diameterOfBinaryTree(TreeNode* root)
{
    if(!root) return 0;
    int maxPath=0;
    dfs(root,maxPath);
    return maxPath;
}