Diameter Of Tree

发表于 | 分类于

Diameter Of Tree(找到树中两个叶节点的最远距离)

题目描述：

给定一棵树的头结点，找到树中的两个节点，要求这两个节点的距离最大，返回该距离。

解题思路：

通过分析我们可以知道，一棵树的两个节点的最远距离可能来自两种情况：

  • 左节点的最深深度 + 右节点的最深深度，经过根节点；
  • 在左节点为根节点中的两个节点存在最远距离；在右节点为根节点中的两个节点存在最远距离；

我们用height函数找到某个节点的深度；用diameter函数找到以某个节点为根中两个叶节点的最远距离。

代码如下：

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
/**
 * 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 diameterOfBinaryTree(TreeNode* root) {
        if (root == NULL) return 0;
        
        int lh = height(root->left);
        int rh = height(root->right);
        //找到左右节点的最深深度
        
        int ld = diameterOfBinaryTree(root->left);
        int rd = diameterOfBinaryTree(root->right);
        //找到左右节点各自为根中的最远距离
        
        return max(lh + rh, max(ld, rd));
        //返回这两种情况中的最远距离即可
    }
    int height(TreeNode* head){
        if (head == NULL) return 0;
        return 1 + max(height(head->left), height(head->right));
        //递归找到最深深度
    }
};