在此树中：
a
/
b d
/ /
c e f
/
g
从根开始的最长路径将是a-d-f-g
这是我的尝试：
class Node:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def print_path(root):
if not root:
return []
if root.left is None:
return [root.val].append(print_path(root.right))
elif root.right is None:
return [root.val].append(print_path(root.left))
elif (root.right is None) and (root.left is None):
return [root.val]
else:
return argmax([root.val].append(print_path(root.left)), [root.val].append(print_path(root.right)))
def argmax(lst1, lst2):
return lst1 if len(lst1) > len(lst2) else lst2
if __name__ == '__main__':
root_node = Node('a')
root_node.left = Node('b')
root_node.right = Node('c')
root_node.right.right = Node('f')
print print_path(root_node)
main()函数中的树不是我展示的示例。对于此树，预期结果将是 a-c-f 。此树如下所示：
a
/
b c
f
现在，我得到
TypeError: object of type 'NoneType' has no len()
我不确定None如何显示在那里，因为我有基本案例。
谢谢！
这是一个有效的实现：
class Node:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def print_path(root):
rightpath = []
leftpath = []
path = []
if root is None:
return []
if (root.right is None) and (root.left is None):
return [root.val]
elif root.right is not None:
rightpath = [root.val] + print_path(root.right)
elif root.left is not None:
leftpath = [root.val] + print_path(root.left)
return argmax(rightpath, leftpath)
def argmax(lst1, lst2):
return lst1 if len(lst1) > len(lst2) else lst2
root_node = Node('a')
root_node.left = Node('b')
root_node.right = Node('c')
root_node.right.right = Node('f')
print print_path(root_node)
代码的几个问题：
1(在(root.right is None) and (root.left is None)之前检查root.left is None不正确 - 您将永远无法达到(root.right is None) and (root.left is None)
2(而不是立即返回，你想使用递归并比较两个分支，然后返回到目前为止路径最长的分支
3(append附加到位，所以你需要把它存储在一个变量中
编辑：更简洁的实现(见评论(
class Node:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def print_path(root):
rightpath = []
leftpath = []
if root is None:
return []
rightpath = [root.val] + print_path(root.right)
leftpath = [root.val] + print_path(root.left)
return argmax(rightpath, leftpath)
def argmax(lst1, lst2):
return lst1 if len(lst1) > len(lst2) else lst2
root_node = Node('a')
root_node.left = Node('b')
root_node.right = Node('c')
root_node.right.right = Node('f')
print print_path(root_node)
您可以通过允许再增加一个级别的递归并让主逻辑处理之前(令人困惑的(特殊情况来显着简化逻辑：
def print_path(root):
if root is None:
return []
return [root.val] + argmax(print_path(root.right), print_path(root.left))
我的解决方案
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
*Longest Path from root to leaf Node
* */
public class LongestPath {
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
Node root =bt.constructTree(bt);
List path = printPath(root);
Iterator itr = path.iterator();
while (itr.hasNext()){
System.out.print(itr.next() +" ");
}
}
public static List<Integer> printPath(Node root){
if(root ==null){
return null;
}
List<Integer> path = new ArrayList<>();
path.add(root.data);
List result = getMaxList(printPath(root.left), printPath(root.right));
if(result!=null) {
path.addAll(result);
}
return path;
}
public static List<Integer> getMaxList(List<Integer> list1, List<Integer> list2){
if(list1==null && list2==null){
return null;
}
if(list1==null){
return list2;
}
if(list2 == null){
return list1;
}
if(list1.size()> list2.size()){
return list1;
}else {
return list2;
}
}
}
二叉树
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
/* Get width of a given level */
int getWidth(Node node, int level)
{
if (node == null)
return 0;
if (level == 1)
return 1;
else if (level > 1)
return getWidth(node.left, level - 1)
+ getWidth(node.right, level - 1);
return 0;
}
/* UTILITY FUNCTIONS */
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(Node node)
{
if (node == null)
return 0;
else
{
/* compute the height of each subtree */
int lHeight = height(node.left);
int rHeight = height(node.right);
/* use the larger one */
return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);
}
}
/* Driver program to test above functions */
public Node constructTree( BinaryTree tree) {
/*
Constructed binary tree is:
1
/
2 3
/
4 5 8
/
6 7
*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(8);
tree.root.right.right.left = new Node(6);
tree.root.right.right.right = new Node(7);
return tree.root;
}
}
输出1 3 8 7
代码应编辑为：
if (root.right is None) and (root.left is None):
return [root.val]
if root.right is not None:
rightpath = [root.val] + print_path(root.right)
if root.left is not None:
leftpath = [root.val] + print_path(root.left)
return argmax(rightpath, leftpath)
或者递归函数将始终传递 print_path(root.left( 如果 right.root 不是 None。
下面是
一个C++实现。
void longest_root_to_leaf_path(Node *root, std::vector<int> current_path,
std::vector<int> &longest_path) {
if (!root)
return;
current_path.push_back(root->data);
if (root->left == nullptr && root->right == nullptr) {
if (current_path.size() > longest_path.size())
longest_path = current_path;
return;
}
longest_root_to_leaf_path(root->left, current_path, longest_path);
longest_root_to_leaf_path(root->right, current_path, longest_path);
current_path.pop_back();
}
上述程序在另一种情况下是错误的
elif root.left is not None:
leftpath = [root.val] + print_path(root.left)
elif root.right is not None:
rightpath = [root.val] + print_path(root.right)
如果你这样给出，输出将仅变为 [a，b]，这不是预期的输出