题目描述

题目链接

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

示例 :
给定二叉树

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

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

 

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

算法1

(递归) $O(n)$

根据题目描述，需要求出树的最大直径。
不难分析出，树的最大直径为：
某个节点左子树和右子树最大深度的和，即找到某一个节点，分别向左子树深入和右子树深入，找到两边深入的最大值，并求其和的最大值
那么我们遍历整个树，即可找到这样一个最大的节点，即最大直径

那么递归基是什么呢？
我们可以发现，当一个节点还有孩子节点时，那么它的深度是可以继续 +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
/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 0;
        dfs(root, ans);
        return ans;
    }

    int dfs(TreeNode* root, int& ans)
    {
        if( !root) return 0;

        int d1 = root->left ? dfs(root->left, ans) + 1 : 0; //如果有左子树，那么最大深度为左子树的最大深度 + 1， 如果没有，那么最大深度不增加
        int d2 = root->right ? dfs(root->right, ans) + 1 : 0; // 右子树同理
        int maxd = max(d1, d2); // 子树中的最大深度是左子树、右子树最大深度的最大值
        ans = max(ans, d1 + d2); // 对于每个节点，要更新其最大直径，为左右节点最大深度的和
        return maxd;
    }
};