给定一颗二叉树,求二叉树的直径。 直径指树上任意两个节点的树上距离的最大值。 数据范围:节点数量满足 ,树为空时,返回 0-笔试面试资料

这是qklbishe.com第18789 篇笔试面试资料
提供答案分析,通过本文《给定一颗二叉树,求二叉树的直径。
直径指树上任意两个节点的树上距离的最大值。
数据范围:节点数量满足 ,树为空时,返回 0-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

给定一颗二叉树,求二叉树的直径。
直径指树上任意两个节点的树上距离的最大值。
数据范围:节点数量满足 给定一颗二叉树,求二叉树的直径。          直径指树上任意两个节点的树上距离的最大值。          数据范围:节点数量满足 ,树为空时,返回 0,树为空时,返回 0
Java

给定一颗二叉树,求二叉树的直径。          直径指树上任意两个节点的树上距离的最大值。          数据范围:节点数量满足 ,树为空时,返回 0 零葬

树型DP套路。对于以某个节点为根节点的子树,有如下两种情况:
                                  给定一颗二叉树,求二叉树的直径。          直径指树上任意两个节点的树上距离的最大值。          数据范围:节点数量满足 ,树为空时,返回 0
  1. 当前节点不参与路径,此时左右子树中最大路径较大的那个就是当前节点不参与路径时的最长路径。如上图红色节点(根节点)的子树中,最长路径就是两个黄色节点经过蓝色节点的路径,并未经过红色节点自身。
  2. 当前节点参与路径,此时最大的路径应该是:左树高+右树高+1(1为当前节点)。如上图中蓝色节点的子树中,最长路径就是两个黄色节点经过自己的那条路径。

这时候对于某个节点而言,只要向左右孩子节点收集信息,就能够计算它的最大路径,需要的信息有:(1) 左子树高度;(2) 右子树高度;(3) 左右孩子的最长路径。根据信息(3)我们可以求得当前节点不参与路径时的最长路径;根据信息(1)和(2)我们可以求得当前节点参与路径时的最长路径。而为了在根节点汇总整棵树的信息,每个节点需要把当前收集到的信息做一个汇总,方便自己的父节点使用:

  1. 计算以当前节点为根节点的子树高度:height=max(left_height, right_height)+1
  2. 以当前节点为根节点的子树所包含的最大路径长度:max(左子树最大路径, 右子树最大路径, 左树高+右树高+1)
但是本题的路径长度并不是节点个数,而是边的条数,因此最终的结果需要-1,且保证不为负数
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);     } }

今天 09:50:46 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定一颗二叉树,求二叉树的直径。 直径指树上任意两个节点的树上距离的最大值。 数据范围:节点数量满足 ,树为空时,返回 0-笔试面试资料

提供最优质的资源集合

立即查看 了解详情