最权威的做网站设计哪家好,企业解决方案搞笑,商城小程序开源,手机视频网站建站分析#xff1a;
暴力求每一段距离也可。 对于以本节点为根的二叉树#xff0c;最远距离有三种可能#xff1a;
1#xff09;最远路径来自左子树 2 #xff09;最远路径来自右子树#xff08;图示与左子树同理#xff09;
3#xff09;最远路径为左右子树距离根最远…
分析
暴力求每一段距离也可。 对于以本节点为根的二叉树最远距离有三种可能
1最远路径来自左子树 2 最远路径来自右子树图示与左子树同理
3最远路径为左右子树距离根最远的两个节点经过根结点连起来。
多种最长路径 需要的信息
1左子树的最远路径长度
2右子树的最远路径长度
3左右子树的深度深度即最远节点 定义结点 public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}
构造返回值信息 public static class ReturnType{public int maxDistance;//最长距离public int h; //高度public ReturnType(int m, int h) {this.maxDistance m;;this.h h;}}
求解过程比较好写了 public static ReturnType process(Node head) {if(head null) {return new ReturnType(0,0);}//收信息ReturnType leftReturnType process(head.left);ReturnType rightReturnType process(head.right);int includeHeadDistance leftReturnType.h 1 rightReturnType.h;//情况3int p1 leftReturnType.maxDistance;int p2 rightReturnType.maxDistance;int resultDistance Math.max(Math.max(p1, p2), includeHeadDistance);//最长距离int hitself Math.max(leftReturnType.h, leftReturnType.h) 1; //树的高度等于子树高度1return new ReturnType(resultDistance, hitself);}
优化
其实我们不需要返回左右子树深度可以用一个全局变量记录。遇到NULL把变量记为0不影响接下来的计算。
用一个含一个元素的数组来记录。因为某些二叉树题目不只需要一个信息所以要利用全局数组。 public static int posOrder(Node head, int[] record) {if (head null) {record[0] 0;//重要return 0;}//取信息int lMax posOrder(head.left, record);int maxfromLeft record[0];int rMax posOrder(head.right, record);int maxFromRight record[0];int curNodeMax maxfromLeft maxFromRight 1;//情况3record[0] Math.max(maxfromLeft, maxFromRight) 1;return Math.max(Math.max(lMax, rMax), curNodeMax);}
最后放上全部代码
package q;public class Demo {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}public static int maxDistance(Node head) {int[] record new int[1];return posOrder(head, record);}public static class ReturnType{public int maxDistance;//最长距离public int h; //高度public ReturnType(int m, int h) {this.maxDistance m;;this.h h;}}public static ReturnType process(Node head) {if(head null) {return new ReturnType(0,0);}//收信息ReturnType leftReturnType process(head.left);ReturnType rightReturnType process(head.right);int includeHeadDistance leftReturnType.h 1 rightReturnType.h;//情况3int p1 leftReturnType.maxDistance;int p2 rightReturnType.maxDistance;int resultDistance Math.max(Math.max(p1, p2), includeHeadDistance);//最长距离int hitself Math.max(leftReturnType.h, leftReturnType.h) 1; //树的高度等于子树高度1return new ReturnType(resultDistance, hitself);}public static int posOrder(Node head, int[] record) {if (head null) {record[0] 0;//重要return 0;}//取信息int lMax posOrder(head.left, record);int maxfromLeft record[0];int rMax posOrder(head.right, record);int maxFromRight record[0];int curNodeMax maxfromLeft maxFromRight 1;//情况3record[0] Math.max(maxfromLeft, maxFromRight) 1;return Math.max(Math.max(lMax, rMax), curNodeMax);}public static void main(String[] args) {Node head1 new Node(1);head1.left new Node(2);head1.right new Node(3);head1.left.left new Node(4);head1.left.right new Node(5);head1.right.left new Node(6);head1.right.right new Node(7);head1.left.left.left new Node(8);head1.right.left.right new Node(9);System.out.println(maxDistance(head1));Node head2 new Node(1);head2.left new Node(2);head2.right new Node(3);head2.right.left new Node(4);head2.right.right new Node(5);head2.right.left.left new Node(6);head2.right.right.right new Node(7);head2.right.left.left.left new Node(8);head2.right.right.right.right new Node(9);System.out.println(maxDistance(head2));}}
