{1,2,3,#,#,4,5}3
{1,2,3,#,#,4,5,9,#,#,6,#,7,#,8}6
{1,2,3}2
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
class Info {
public int maxDistance;
public int height;
public Info(int maxDistance, int height) {
this.maxDistance = maxDistance;
this.height = height;
}
}
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
public int diameterOfBinaryTree (TreeNode root) {
// write code here
return Math.max(process(root).maxDistance - 1, 0);
}
private Info process(TreeNode node) {
if(node == null){
return new Info(0, 0);
}
// 向左右子树收集信息
Info leftInfo = process(node.left);
Info rightInfo = process(node.right);
int path1 = leftInfo.height + rightInfo.height + 1; // 头结点参与的距离
int path2 = Math.max(leftInfo.maxDistance, rightInfo.maxDistance); // 头结点不参与的距离
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
return new Info(Math.max(path1, path2), height);
}
} 
int max = 0;
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
public int diameterOfBinaryTree (TreeNode root) {
if(root == null) return 0;
max = Math.max(max, maxC(root.left) + maxC(root.right));
diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);
return max;
}
/**
* 某个节点的最大层数
*/
private int maxC(TreeNode root) {
if(root == null) return 0;
return Math.max(maxC(root.left), maxC(root.right)) + 1;
} import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int max=0;
public int diameterOfBinaryTree (TreeNode root) {
// write code here
getDepth(root);
return max;
}
public int getDepth(TreeNode root){
if(root==null){
return 0;
}
int left=getDepth(root.left);
int right=getDepth(root.right);
max=Math.max((left+right),max);
return Math.max(left,right)+1;
}
} class Solution: def diameterOfBinaryTree(self , root: TreeNode) -> int: # write code here def height(root): # 返回该节点的深度 if not root: return 0 return max(1 + height(root.left), 1 + height(root.right)) l = [] def dfs(root): # 遍历二叉树，将每个节点的直径放入列表 if not root: return # 直径 = 左子树深度 + 右子树深度 diameter = height(root.left) + height(root.right) l.append(diameter) dfs(root.left) dfs(root.right) dfs(root) return max(l) if len(l) > 0 else 0
package main
// import "fmt"
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
func diameterOfBinaryTree( root *TreeNode ) int {
if root==nil{
return 0
}
return max(cal(root.Left)+cal(root.Right),max(cal(root.Left),cal(root.Right)))
}
func cal(root *TreeNode)int{
if root==nil{
return 0
}
cnt:=1
cnt+=max(cal(root.Left),cal(root.Right))
return cnt
}
func max(a,b int)int{
if a>b{
return a
}
return b
}
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
//以 root 为头结点的树，最大直径就是左右两个子树的高度相加
int dfs(struct TreeNode* root){
if(NULL==root)
return 0;
else{
return (dfs(root->left)>dfs(root->right)?dfs(root->left):dfs(root->right))+1;
}
}
int diameterOfBinaryTree(struct TreeNode* root ) {
// write code here
if(root==NULL)
return NULL;
return dfs(root->left)+dfs(root->right);
} 
mlgb的下次别给的case和数据范围不一致好不好 说好的100个点给了1000个点。100个点就不一定树形dp了好吧，随便一个floyd都可以干了。 
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int diameterOfBinaryTree(TreeNode* root) {
// write code here
if(root == NULL) return 0;
return max(max(diameterOfBinaryTree(root->left),diameterOfBinaryTree(root->right)),lengthOfBinaryTree(root->left) + lengthOfBinaryTree(root->right));
}
int lengthOfBinaryTree(TreeNode* root){
if(root == NULL) return 0;
return 1 + max(lengthOfBinaryTree(root->left),lengthOfBinaryTree(root->right));
}
}; # -*- coding: utf-8 -*- import sys class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class BT(object): def __init__(self): self.root = None def levelOrderToBT(self, nums): n = len(nums) if n > 0: self.root = TreeNode(nums[0]) queue, idx = [self.root], 1 while queue and idx < n: curNode = queue.pop(0) curNode.left = TreeNode(nums[idx]) \ if nums[idx] != None else None if curNode.left: queue.append(curNode.left) curNode.right = TreeNode(nums[idx + 1]) \ if idx + 1 < n and nums[idx + 1] != None else None if curNode.right: queue.append(curNode.right) idx += 2 return self.root @staticmethod def levelOrder(root): if not root: return [] queue, res = [root], [] while queue: node = queue.pop(0) if node: res.append(node.val) queue.append(node.left) queue.append(node.right) else: res.append(None) while res and res[-1] == None: res.pop() return res # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param root TreeNode类 # @return int整型 # class Solution: """ 题目： NC195 二叉树的直径 https://www.nowcoder.com/practice/15f977cedc5a4ffa8f03a3433d18650d?tpId=117&&tqId=39370&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking 参考： 大神：君无颜 算法： 关键点：以当前节点为头结点的树，直径就是左右两个子树的高度相加，故最大直径属于在如下三种情况之一： 1. 最大直径包含root：以 root 为头结点的树，最大直径就是左右两个子树的高度相加 2. 最大直径出现在root的左子树：左子树的直径是以 root->left 为头结点的树，最大直径同理 3. 最大直径出现在root的右子树：右子树的直径是以 root->right 为头结点的树，最大直径同理 最后，取三者最大值即可。 复杂度： 时间复杂度：O(N)，N为二叉树的节点数 空间复杂度：O(H)，H为二叉树的高度 """ def diameterOfBinaryTree(self, root): # write code here def getHeight(root): if not root: # 空子树的高度为0 return 0 lHeight, rHeight = getHeight(root.left), getHeight(root.right) self.res = max(self.res, lHeight + rHeight) return lHeight + 1 if lHeight > rHeight else rHeight + 1 self.res = 0 sys.setrecursionlimit(1500) getHeight(root) return self.res if __name__ == '__main__': s = Solution() # nums = [1, 2, 3, None, None, 4, 5] # nums = [1, 2, 3, None, None, 4, 5, 9, None, None, 6, None, 7, None, 8] # nums = [1, 2, 3] nums = [] bt = BT() bt1 = bt.levelOrderToBT(nums) # print BT.levelOrder(bt1) res = s.diameterOfBinaryTree(bt1) print res
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int diameterOfBinaryTree(TreeNode* root) {
// write code here
if(!root) return 0;
int Lmax = 0;
search(root, Lmax);
return Lmax;
}
int search(TreeNode* node, int & Lmax)
{
if(!node) return 0;
int left = search(node->left, Lmax);
int right = search(node->right, Lmax);
Lmax = Lmax < left + right ? left + right : Lmax;
return max(left, right) + 1;
}
}; 
//后序遍历
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int res = 0;
int diameterOfBinaryTree(TreeNode* root) {
// write code here
dfs(root);
return res;
}
int dfs(TreeNode* root){
if(!root) return 0;
int l = dfs(root->left) ;
int r = dfs(root->right) ;
res = max(res,l + r);
return max(l,r) + 1;
}
}; 
class Solution {
public:
int res1 = 0;
int diameterOfBinaryTree(TreeNode* root) {
// write code here
diameter(root);
return res1;
}
int diameter(TreeNode* root) {
if(root == nullptr) return 0;
int left= diameter(root->left);
int right= diameter(root->right);
res1 = (left+right)>res1?(left+right):res1;
return left>right?left+1:right+1;
}
}; class Solution: def diameterOfBinaryTree(self , root: TreeNode) -> int: # 递归+计算树的最大深度 self.best=0 def depth(root): if not root: return 0 left=depth(root.left) right=depth(root.right) self.best=max(self.best,left+right) return max(left,right)+1 de=depth(root) return self.best
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
