LeetCode Daily Question 20

4 月 8 日 每日一题

题目：1245. Tree Diameter

The diameter of a tree is the maximum number of edges on any path connecting two nodes of the tree. For example, here are three sample trees and their diameters. In each case, the longest path is bolded and shown in purple. Note that there may be more than one longest path.

Implement the diameter() function, which computes the diameter of a binary tree represented by a pointer to an object of the BinaryTreeNode class. Assume that nullptr represents an empty tree or a missing child. You may write helper functions.

思路

本道题是关于 tree 的递归题目。首先对问题进行分解，寻找问题和子问题的关系。
我们需要获得当前最大的 Diameter，它可能来自当前节点，左节点或右节点。
即 tempDia = max (leftDia, rightDia, tempDia)。而 Dia 等于 leftHeight + rightHeight + 1。
因此，我们需要先计算 height，height 等于 1 + max(leftHeight, rightHeight)。
为了将时间复杂度简化到 On，建立 struct 同时储存 Hight 和当前 Diameter，在一个递归函数中可以同时完成上面提到的两个问题。
临界条件为 nullpointer，返回{1,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
28
29
30
31
32

#define min(a,b)            (((a) < (b)) ? (a) : (b))
#define max(a,b)            (((a) > (b)) ? (a) : (b))

struct BinaryTreeNode {
  BinaryTreeNode* left;
  BinaryTreeNode* right;
  int value;
  BinaryTreeNode(int n) : left{nullptr}, right{nullptr}, value{n} {}
};

struct NodeInfo{
    int height;
    int diameter;
};

NodeInfo helper(const BinaryTreeNode* tree){
    if(!tree){
        return NodeInfo{0,0};
    }
    NodeInfo left = helper(tree->left);
    NodeInfo right = helper(tree->right);
    int childrenDia = max(left.diameter, right.diameter);
    int selfDia = 1 + left.height + right.height;
    int tempDia = max(childrenDia, selfDia);
    return NodeInfo{ 1 + max(left.height , right.height), tempDia};
}

int diameter(const BinaryTreeNode* tree) {
    return helper(tree).diameter;
}