二叉树最长路径
二叉树 路径 最长
2023-09-27 14:25:54 时间
分析:
暴力求每一段距离也可。
对于以本节点为根的二叉树,最远距离有三种可能:
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));
}
}
相关文章
- 平衡二叉树、B树、B+树、B*树、LSM树简介
- 数据结构 | 二叉树的一些性质及证明、树的路径长度、结点的路径长度
- LeetCode搜索二叉树的练习
- 98、【树与二叉树】leetcode ——112. 路径总和:5行精简代码回溯法[带剪枝]+迭代法(C++版本)
- 93、【树与二叉树】leetcode ——222. 完全二叉树的节点个数:普通二叉树求法+完全二叉树性质求法(C++版本)
- 【剑指offer】Q25:二叉树中和为某一值的路径
- [LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历
- [LeetCode] 111. Minimum Depth of Binary Tree 二叉树的最小深度
- 数据结构:树的概念以及二叉树的实现
- LeetCode二叉树路径总和
- LeetCode平衡二叉树
- 数据结构 树、二叉树、查找算法总结
- leetcode 257. Binary Tree Paths 二叉树的所有路径(简单)
- leetcode算法257.二叉树的所有路径