二叉树的直径

题目描述：给你一棵二叉树的根节点，返回该树的 直径 。二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

提示：

• 树中节点数目在范围 [1, 104] 内

• -100 <= Node.val <= 100

way：任意一条从一个节点到另一个节点的直径的节点数都可以看成是从一个节点出发，加上它的左子树的深度和右子树的深度，所以可以后序得到每一个节点的这样的值然后取max就是节点数的最大值，那么直径就是节点数-1。时间复杂度O(n)，空间复杂度O(h)。

/**
 * 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 ans = -1;

    int getNodeDepth(TreeNode * root)
    {
        if(root == nullptr) return 0;
        int left = getNodeDepth(root->left);
        int right = getNodeDepth(root->right);
        ans = max(ans, left + right + 1);
        return max(left, right) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        getNodeDepth(root);
        return ans -1;
    }
};

way：如果是求以x为根节点的二叉树的直径的话，那么这条直径可能经过x，也可能不经过x，如果这条直径经过x，那么直径的节点数就是左子树的深度+右子树的深度+1，如果这条直径不经过x，那么直径的节点数就是x的左子树中距离最远的2个节点之间的节点数或者右子树中距离最远的2个节点之间的节点数，这么看的话，如果x想要向左右子树分别要信息然后得到自身信息返回的话，需要的信息有树上最远的2个节点之间的节点数（也就是直径的节点数），树的高度。

/**
 * 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) {}
 * };
 */

struct Info{
    int maxDis;
    int height;
    Info(int maxDis, int height)
    {
        this->maxDis = maxDis;
        this->height = height;
    }
};


class Solution {
public:
    Info getInfo(TreeNode * root)
    {
        if(root == nullptr) return Info(0,0);
        Info left = getInfo(root->left);
        Info right = getInfo(root->right);
        int height = max(left.height, right.height) +1;
        int maxDis;
        int p1 = left.height+right.height+1;
        int p2 = left.maxDis;
        int p3 = right.maxDis;
        maxDis = max(p1, max(p2, p3));
        return Info(maxDis, height);
    }

    int diameterOfBinaryTree(TreeNode* root) {
        return getInfo(root).maxDis -1;
    }
};

我说的二叉树的深度和高度指的都是节点数，比如一个节点的二叉树的深度和高度都是1，不是指边的长度。