搞网站开发的程序员属于哪一类,网站收录入口,江苏省建设工程一站式申报网站,合肥网站建设服务543. 二叉树的直径 - 力扣#xff08;LeetCode#xff09; 一、题目
给定一棵二叉树#xff0c;你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 : 给定二叉树 1 / \ 2 3 … 543. 二叉树的直径 - 力扣LeetCode 一、题目
给定一棵二叉树你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意两结点之间的路径长度是以它们之间边的数目表示。
二、代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int diameterOfBinaryTree(TreeNode root) {return process(root).maxDistance - 1;}// 信息类public class Info {// 当前树的最大距离public int maxDistance;// 当前树的高度public int height;public Info(int m, int h) {maxDistance m;height h;}}// 二叉树递归求解public Info process(TreeNode x) {// 如果是一个空树那么这棵树的最大距离就是0高度也是0 递归出口if (x null) {// 这个就属于空置比较好处理的所以就不向上返回null让上层去处理了而是直接在本层创建好对应的info返回return new Info(0, 0);}// 左右子树向下递归 向下递归的位置// 递归返回左子树的infoInfo leftInfo process(x.left);// 递归返回右子树的infoInfo rightInfo process(x.right);// 当前树的告诉就是左右子树最大高度 1int height Math.max(leftInfo.height, rightInfo.height) 1;// 左树最大距离int p1 leftInfo.maxDistance;// 右树最大距离int p2 rightInfo.maxDistance;// 左树最大高度 右树最大高度 1int p3 leftInfo.height rightInfo.height 1;// 当前树的最大距离就是p1、p2、p3中最大值int maxDistance Math.max(Math.max(p1, p2), p3);// 创建当前树的info并返回 连接每一层递归的接口return new Info(maxDistance, height);}}
三、解题思路
根据题意列出来可能性。将这道题抽象成求以X为根节点的树的最大距离
可能性分类1、最大距离与X无关 2、最大距离与X有关。
1、与X无关
也就是说X树上最大距离的路径是不通过X的那么X树的最大距离就是X左子树最大距离和X右子树最大距离的最大值
2、与X有关
也就是说X树上最大距离的路径是通过X的那么X树的最大距离就是 x左树离自己最远的点 1 右树上离自己最远的点。即X左子树的高度 X右子树的高度 1 就是X树的最大距离。
通过分类我们就在知道在计算X树的最大距离是应该需要其左右子树提供哪些信息我们就知道了该如何对X左右子树提要求进而设计info类。我们需要他们提供自己的高度和最大距离。
