题目描述

blablabla

样例

blablabla

算法1

(递归) $O(n)$

感觉这个题最精髓的就是这两行代码了， 因为题目要求我们算的直径考虑的是最长的边，而不是最长的 path 的node数目，如果是统计最长的 path 的 node 数目，每次递归的时候加 1 就好了，但是因为这里算的是边长， 所以在走到叶子节点的时候统计的长度是 0， 如果不是叶子节点就是1加上下一层调用该函数的返回值。

int left = root->left ? 1 + help(root->left, res) : 0;
int right = root->right ? 1 + help(root->right, res) : 0;

时间复杂度分析：o(n)

C++ 代码

/**
 * 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) {
        int res = 0;
        help(root, res);
        return res;
    }
private:
    int help(TreeNode* root, int& res) {
        if (!root) {
            return 0;
        }

        int left = root->left ? 1 + help(root->left, res) : 0;
        int right = root->right ? 1 + help(root->right, res) : 0;
        int maxDepth = max(left,  right);
        res = max(res, left + right);
        return maxDepth;
    }

};