在二叉树中打印从root开始的最长路径

Question

在这棵树上:

     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因为我有基本情况,所以我不确定那里是怎么出现的.

谢谢!

Answer 1

这是一个有效的实现:

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.left is None之前检查(root.right is None) and (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)