Leetcode:543. 二叉树的直径

Leetcode:543. 二叉树的直径

Talk is cheap . Show me the code .

/**
 * 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 cnt=-1;
    int getHeight(TreeNode* root,int& height){//自顶向上写法
        if(root==NULL){
            height=0;
            return 0;
        } 
        int left,right;
        getHeight(root->left,left),getHeight(root->right,right);
        height=max(left,right)+1;
        if(left+right>cnt) cnt=left+right;
        return cnt;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int height=0;
        return getHeight(root,height);
    }
};