LeetCode 543. 二叉树的直径 （递归、求二叉树的深度）

二叉树的直径
思路①：
这种写法完全是基于递归的想法：

• 路径如果经过根节点，最长路径应该是左右子树高度之和。
• 如果不经过，那么去看如果经过左子树的跟、经过右子树的根的最长长度。（相同问题，递归解决）
  不过，这种写法有很多冗余的遍历。

/**
 * 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){
            return 0;
        }
        int p1 = getHeight(root->left)+getHeight(root->right);
        int p2 = diameterOfBinaryTree(root->left);
        int p3 = diameterOfBinaryTree(root->right);
        return max(p1,max(p2,p3));
    }
    int getHeight(TreeNode* root){
        if(!root){
            return 0;
        }
        return 1+max(getHeight(root->left),getHeight(root->right));
    }
};

思路②
对思路①进行改进，遍历整棵树，用ans变量记录下每个节点的左右子树高度之和的最大值即可。

/**
 * 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 ans = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root){
            return 0;
        }
        getHeight(root);
        return ans-1;
    }
    int getHeight(TreeNode *root){
        if(!root){
            return 0;
        }
        int l = getHeight(root->left);
        int r = getHeight(root->right);
        ans = max(ans,l+r+1);
        return 1+max(l,r);
    }
};