二叉树最长路径
【摘要】
分析：
暴力求每一段距离也可。
对于以本节点为根的二叉树，最远距离有三种可能：
1）最远路径来自左子树
2 ）最远路径来自右子树（图示与左子树同理）
3）最远路径为左右子树距离根最远的两个节点，经过根结点连起来。
（多种最长路径）
需要的信息：
1）左子树的最远路径长度
2）右子树的最远路径长度
3）左右子树的深度（...
分析：
暴力求每一段距离也可。
对于以本节点为根的二叉树，最远距离有三种可能：
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;//情况3
-
int 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; //树的高度等于子树高度+1
-
-
return 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;//情况3
-
record[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;//情况3
-
int 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; //树的高度等于子树高度+1
-
-
return 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;//情况3
-
record[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));
-
-
}
-
-
}
-
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/84254502
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）