[leetcode]-543. Diameter of Binary Tree

比眉伴天荒 2022-06-18 01:09 245阅读 0赞

Center

思路：

diameter保存最大的直径，每次更新该值

depthOfBinary利用分治算法计算树的深度：分解为子问题，分别求得左右子树的深度lDepth,rDepth，两者相加+2就是该节点下的最大直径。

代码：

  1. class Solution {
  2. public:
  3.     int diameter = 0;
  4.     int diameterOfBinaryTree(TreeNode* root) {
  5.         depthOfBinaryTree(root);
  6.         return diameter;
  7.     }
  8.     int depthOfBinaryTree(TreeNode* root){
  9.         if(root == NULL){
  10.             return -1;
  11.         }
  12.         int lDepth = depthOfBinaryTree(root->left);
  13.         int rDepth = depthOfBinaryTree(root->right);
  14.         diameter = max(diameter,lDepth+rDepth+2);
  15.         return max(lDepth, rDepth) + 1;
  16.     }
  17. };

发表评论

表情：
评论列表 （有 0 条评论，245人围观）

还没有评论，来说两句吧...

相关阅读