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 回答
3

您可以通过允许更多级别的递归并让主逻辑处理之前的（令人困惑的）特殊情况来显着简化您的逻辑：

def print_path(root):
    if root is None:
        return []
    return [root.val] + argmax(print_path(root.right), print_path(root.left))
于 2016-02-17T04:28:48.113 回答
0

代码应编辑为：

 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)

或者如果 right.root 不是 None，递归函数将始终传递 print_path(root.left)。

于 2016-11-11T07:32:30.210 回答
0

我的解决方案

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

于 2017-01-25T14:41:37.920 回答
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 回答
-1

上面的程序在另一种情况下是错误的 

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] ，这不是预期的输出

于 2016-11-08T09:56:34.137 回答