【Leetcode】543. Diameter of Binary Tree

Myth丶恋晨 2022-09-30 07:28 240阅读 0赞

思路：

定义一个类变量diameter，保存最大diameter值。

通过递归计算左右子树的深度来计算根节点的diameter（记为temp），通过和类变量 diameter 进行比较，保存较大值。

在每一次递归结束后，返回左右子树的深度，将二者相加再加2就是根节点的diameter。 

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.     int diameter = 0;
  12.     public int diameterOfBinaryTree(TreeNode root) {
  13.         getDepth(root);
  14.         return diameter;
  15.     }
  16.     public int getDepth(TreeNode root){
  17.         if (root == null)
  18.             return -1;
  19.         int left = getDepth(root.left);
  20.         int right = getDepth(root.right);
  21.         int temp = left + right + 2;
  22.         if (temp > diameter)
  23.             diameter = temp;
  24.         return Math.max(left, right) + 1;
  25.     }
  26. }

Runtime：10ms

发表评论

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

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

相关阅读