6

このツリーでは:

     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基本ケースがあるため、そこにどのように表示されるかわかりません。

ありがとう！

4

6 に答える 6

9

これが実用的な実装です：

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)
于 2016-02-17T01:37:57.960 に答える
0

以下は 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();                                               
}
于 2020-05-03T11:44:12.597 に答える