Leetcode 543.二叉树的直径【C++】

地址：https://leetcode-cn.com/problems/diameter-of-binary-tree/

题目

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

示例 :
给定二叉树

      1
     / \
    2   3
   / \     
  4   5    

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

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

解题思路

首先这个题需要注意一点，整棵树的最长路径，不一定是左右子树的深度相加，因为可能最长路径并没有经过根结点。但是可以确定的是，最长路径一定是某一个结点作为根节点的左右子树的深度相加。

所以如果求出每一个结点作为根结点的左右子树的深度，也就可以找出所有可能的最长路径，只需要不断更新最大长度即可。

代码

/**
 * 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 maxLength = 0;//最大长度

    int diameterOfBinaryTree(TreeNode* root) {
        //如果树为空则长度为0
        if (root == NULL)
            return 0;
        getDepth(root);
        return maxLength;
    }

    //获取深度
    int getDepth(TreeNode* root) {
        //树空则深度为0
        if (root == NULL)
            return 0;
        int leftDepth = getDepth(root->left);//左子树深度
        int rightDepth = getDepth(root->right);//右子树深度
        //当前树的左右深度相加即经过根结点的最长路径（但不是整棵树的最长路径）
        //整棵树的最长路径需要根据经过每一个结点作为根结点并且经过该根结点的最长路径动态更新
        maxLength = max(maxLength, leftDepth + rightDepth);
        return max(leftDepth, rightDepth) + 1;//+1即当前根结点到父节点之间的路径
    }
};