二叉树的直径

备注

重点在理解递归算法的作用, 向上传递子树的值.

class Solution {
  int sum;

  int post(TreeNode *root) {
    if (!root)
      return 0;
    int left = post(root->left);
    int right = post(root->right);
    sum = max(sum, left + right);
    return max(left, right) + 1;
  }

public:
  int diameterOfBinaryTree(TreeNode *root) {
    sum = 0;
    post(root);
    return sum;
  }
};