NC195 二叉树的直径
二叉树的直径
https://www.nowcoder.com/practice/15f977cedc5a4ffa8f03a3433d18650d?tpId=196&tqId=39376&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Ftab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
思路：首先观察直径是由左右子树的深度相加得到的，所以先写出递归求二叉树深度的函数getDepth()，递归体是（本层节点，左子树，右子树）三者的最大直径。
import java.util.*;
public class Solution {
public int getDepth(TreeNode root){
if(root==null)return 0;
return Math.max(getDepth(root.left)+1,getDepth(root.right)+1);
}
public int diameterOfBinaryTree (TreeNode root) {
if (root==null) return 0;
int nowDepth = getDepth(root.left)+getDepth(root.right);
int childDepth = Math.max(diameterOfBinaryTree(root.left),diameterOfBinaryTree(root.right));
return Math.max(nowDepth,childDepth);
}
}
