我正在解决一个问题，我必须在二叉树中找到最长的叶到叶路径及其长度。
例如，如果二叉树如下：
a
/\
b c
/ / \
d e f
/ \ \
g h p
\
k
最长的叶到叶路径是khdbacfp，其长度为8。
我通过递归查找左右子树的长度来计算长度，然后return height_left + height_right + 1. 我的概念正确吗？
另外我应该如何打印最长的叶子到叶子的路径？我只是想要一个想法继续进行。
在我看来，这个算法非常接近于找到二叉树的直径。树的直径是树中两个叶子之间最长路径上的节点数。
我认为您可以在此处查找实现：http ://www.geeksforgeeks.org/diameter-of-a-binary-tree/ ，然后根据需要对其进行调整或优化其时间复杂度。但我认为O(n)已经足够好了。
网上的大多数答案都给出了如何找到树的直径，即如何找到最长路径中的节点数。
唯一的补充是我们需要存储对其有贡献的节点。
在递归中，这可以通过两种方式完成。
a) 它应该是一个返回类型
b) 它应该是一个输入参数，它是一个对象。该对象在递归过程中填充了结果。
不需要打印最长路径，我们只需要检查每个节点：
Max of
1) 左节点最大路径
2) 右节点最大路径
c) 当前节点最大路径（需要更多输入）
现在，要计算当前节点最大路径，我们需要更多输入：
当前节点最大路径需要：
1) 最大左节点高度
2) 最大右节点高度
这可以存储在节点本身中（作为高度参数），也可以通过递归传递。
这只会给出最长路径的直径/长度。
现在，要打印路径，我们需要存储更多信息，即：
-List<Nodes> pathList这包含迄今为止形成最长路径的节点（注意这可能不包含当前节点）。
- List<Nodes> heightList- 这包含形成从节点到其叶子的最长高度的节点。
最后是算法：
//方法的输入和输出
class Node{
int value;
Node leftchild;
Node rightchild;
}
class ReturnInfo{
ReturnInfo(){
maxpathlen = 0;
maxheight = 0;
pathList = new ArrayList<Node>();
heightList = new ArrayList<Node>();
}
int maxpathlen; //current max path
int maxheight; //current max height
List<Nodes> pathList;
List<Nodes> heightList;
}
//签名 public ReturnInfo getMaxPath(Node n);
//执行
public ReturnInfo getMaxPath(Node n){
//Base case
if(n==null) return new ReturnInfo();
//This is a bottom up recursion. Info will flow from leaves to root.
//So first recurse and then do the work at this node level
//Recurse left & right
ReturnInfo leftReturnInfo = getMaxPath(n.leftchild);
ReturnInfo rightReturnInfo = getMaxPath(n.rightchild);
//Do work in this recursion or for this node
ReturnInfo retInfo = new ReturnInfo();
//Update all 4 parameters of returninfo and we are done
retInfo.maxheight = max(leftReturnInfo.maxheight, rightReturnInfo.maxheight) + 1;
//Update retInfo.heightList accordingly
retInfo.heightList = ....
retInfo.maxPathLen = max(leftReturnInfo.maxPathLen, rigthReturnInfo.maxPathLen, leftReturnInfo.maxHeight+rightReturnInfo.maxHeight+1);
//Remember from where maxPathLen came from and update accordingly
retInfo.pathList = .....
return retInfo;//We are done
}
defintion:
node: (char content, node left , node right , node parent)
add(list , node): add node as last element in list
remove(list , index): remove and return element at index in list
length(string): length of string
insert(string , char , index): insert char at index in string
concat(string a , string OR char b): append b to a
input: node start
output: string
start
list nodes
node n
add(nodes , start)
do
n = remove(nodes , 0)
if n.parent != null
add(nodes , n.parent)
if n.left != null
add(nodes , n.left)
if n.right != null
add(nodes , n.right)
while !isEmpty(nodes)
//n now is the node with the greatest distance to start
string left = ""
string right = ""
node a = start
node b = n
while(a != b)
insert(left , a.content , length(left) - 1)
insert(right , b.content , 0)
a = a.parent
b = b.parent
string result = left
concat(result , a.content)
concat(result , right)
return result
您需要一个返回子树中最长分支和最长路径的函数：
PS：我省略了细节（例如边界条件等）。但这应该给你一个想法。这个函数返回两个东西“分支”和“路径”。“分支”是从该节点到其任何叶子的最长路径。“路径”是该子树中任意两个叶子之间的最长路径。
def longestPath(node):
(leftBranch, leftPath) = longestPath(node.left);
(rightBranch, rightPath) = longestPath(node.right);
if len(rightBranch) > len(leftBranch):
curBranch = rightBranch+node.name
else:
curBranch = leftBranch+node.name
curPath = leftBranch + node.name + rev(rightBranch)
bestPath = curPath
if len(leftPath) > length(bestPath):
bestPath = leftPath
if len(rightPath) > length(bestPath):
bestPath = rightPath
return (curBranch, bestPath)
最长的叶子到叶子的路径意味着找到一棵树的直径。可以使用高度函数来完成。
网上有很多解决方案。
/** Searches for the longest possible leaf-to-leaf path in this tree.
*
* Time - O(log^2 n)
* Space - O(log n)
*/
def diameter: List[A] = {
def build(t: Tree[A], p: List[A]): List[A] =
if (t.isEmpty) p
else if (t.left.height > t.right.height) build(t.left, t.value :: p)
else build(t.right, t.value :: p)
if (isEmpty) Nil
else {
val ld = left.diameter
val rd = right.diameter
val md = if (ld.length > rd.length) ld else rd
if (1 + left.height + right.height > md.length)
build(right, value :: build(left, Nil).reverse).reverse
else md
}
}
这个想法很简单：
ld和rd最大'md'）。if (1 + ....)）。build函数构建一条新路径，它会生成从给定节点 't' 到叶子的最长路径。所以，我们只是将这个函数的两个结果（左右孩子）与当前节点连接起来。md。这是我的 Swift 解决方案：
func diameterPath() -> [T] {
return diameterPathHelper(root).Path
}
typealias HeightAndDiameterAndPath = (Height: Int, Diameter: Int, Path: [T])
private func diameterPathHelper(node: TreeNode<T>?) -> HeightAndDiameterAndPath {
guard let node = node else {
return HeightAndDiameterAndPath(0, 0, [])
}
let left = diameterPathHelper(node.left)
let right = diameterPathHelper(node.right)
let height = max(left.Height, right.Height) + 1
if left.Height + right.Height + 1 > max(left.Diameter, right.Diameter) {
let currentDiameter = left.Height + right.Height + 1
let path = left.Path + [node.data] + right.Path
return HeightAndDiameterAndPath(height, currentDiameter, path)
} else {
if left.Diameter > right.Diameter {
return HeightAndDiameterAndPath(height, left.Diameter, left.Path)
} else {
return HeightAndDiameterAndPath(height, right.Diameter, right.Path)
}
}
}
你忽略了一个条件：如果最长的路径不经过根节点怎么办？
static int findLongestPathLength(Node root){
if(root == null)
return 0;
int lh = getHeight(root.left);
int rh = getHeight(root.right);
return Math.max(1+lh+rh,
Math.max(findLongestPathLength(root.left),findLongestPathLength(root.right)));
}
static int getHeight(Node root){
if(root == null)
return 0;
return Math.max(getHeight(root.left)+1, getHeight(root.right)+1);
}
即使它不通过根，这也将确保它找到最长的路径。
We can use the maxdepth approach for this and initialize a variable max as 0.
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return max;
}
private int maxDepth(TreeNode root) {
if (root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
max = Math.max(max, left + right);
return Math.max(left, right) + 1;
}
}