工信部资质查询网站,个人网站设计模板中文,wordpress+Apache升级,做土豆的视频在线观看网站1、题目描述 给定一棵二叉树#xff0c;计算这课二叉树的直径长度#xff0c;即为二叉树任意两个节点间的最长路径。比如#xff1a; 这棵二叉树的最长路径为3。
2、解题思路 使用递归进行求解#xff0c;每次递归的过程中#xff0c;先求出以某个节点为树根的二…1、题目描述 给定一棵二叉树计算这课二叉树的直径长度即为二叉树任意两个节点间的最长路径。比如 这棵二叉树的最长路径为3。
2、解题思路 使用递归进行求解每次递归的过程中先求出以某个节点为树根的二叉树的左子树的最长深度maxLeft、右子树的最长深度maxRight并在递归函数中用一个变量maxLen来保存任意两个节点间的最长路径。在求出左子树的最长深度maxLeft和右子树的最长深度maxRight之后就可以求出以该节点为根的二叉树的最长路径maxLen。具体代码如下
public class Solution {static int maxLen 0;public static void main(String[] args) {TreeNode root new TreeNode(0);TreeNode p1 new TreeNode(1);TreeNode p2 new TreeNode(2);TreeNode p3 new TreeNode(3);TreeNode p4 new TreeNode(4);TreeNode p5 new TreeNode(5);TreeNode p6 new TreeNode(6);TreeNode p7 new TreeNode(7);TreeNode p8 new TreeNode(8);root.left p1;root.right p2;p1.left p3;p3.left p4;p2.left p5;p2.right p6;p6.right p7;p7.right p8;FindMaxLen(root);System.out.println(maxLen);}public static void FindMaxLen(TreeNode pRoot) {if (pRoot null) {// 空的话直接结束return;}if (pRoot.left null) {// 左子为空左面最大长度为0pRoot.maxLeft 0;}if (pRoot.right null) {// 右子为空右面最大长度为0pRoot.maxRight 0;}if (pRoot.left ! null) {// 递归获取以左子节点为根节点的最大距离FindMaxLen(pRoot.left);}if (pRoot.right ! null) {// 递归获取以右子节点为根节点的最大距离FindMaxLen(pRoot.right);}if (pRoot.left ! null) {// 左面最大距离左子左面最大距离与左子右面最大距离取最大值1pRoot.maxLeft Math.max(pRoot.left.maxLeft, pRoot.left.maxRight) 1;}if (pRoot.right ! null) {// 右面最大距离右子左面最大距离与右子右面最大距离取最大值1pRoot.maxRight Math.max(pRoot.right.maxLeft, pRoot.right.maxRight) 1;}if (pRoot.maxLeft pRoot.maxRight maxLen) {// 刷新最大距离maxLen pRoot.maxLeft pRoot.maxRight;}}}class TreeNode {TreeNode left;TreeNode right;int maxLeft;int maxRight;int data;public TreeNode(int data) {this.data data;}
}
3、另一种解法递归
public static int FindMaxLen(TreeNode pRoot) {if (pRoot null) {return 0;}// 递归获取左子、右子的最大距离int maxLeft FindMaxLen1(pRoot.left);int maxRight FindMaxLen1(pRoot.right);// 刷新最大距离maxLen Math.max(maxLeft maxRight, maxLen);// 返回该节点的父节点在该侧的最大距离return Math.max(maxLeft, maxRight) 1;
}
