在二叉树中从根节点开始打印最长路径

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，因为我已经有了基本情况。

谢谢！

- coder_learner

---

如果您展示您正在测量的树（答案为a-c-f的树）而不是其他树，那么这将是一个更容易的问题。 - GlenPeterson

完成 @500-服务器内部错误 - coder_learner

你的树是否自平衡？二叉树可以有很多种形态，如果它不平衡，那么你就必须基本上沿着最左边底部一路跟踪到底部边缘，这将具有与其迟钝程度成比例的复杂度。 - Grady Player

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)

- kevchoi

---

你认为有没有更有效的方法来解决这个问题？ - coder_learner

为了找到树的最大深度，我们必须遍历树中的所有节点，没有其他方法。因此，树的遍历具有O(n)的时间复杂度。您的递归实现就是这样做的，所以我认为没有更有效的方法！ - kevchoi

@kevchoi，我认为你应该删除elif条件，因为1.如果节点是叶子节点，2.如果左子树不为空，3.如果右子树不为空。所以在这里你不应该使用elif条件，因为它会削减一些测试用例... - Neelabh Singh

@kevchoi，我支持@geeks的建议。使用elif语句可以避免不必要地进入root.left is not None条件判断。 - Imjohsep

Answer 2

你可以通过允许一层递归来显著简化你的逻辑，并让主要逻辑处理以前（令人困惑的）特殊情况。

def print_path(root):
    if root is None:
        return []
    return [root.val] + argmax(print_path(root.right), print_path(root.left))

- cdlane

Answer 3

我的解决方案

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

- Neelabh Singh

Answer 4

代码应该被编辑为：

 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)。

- Boxi

Answer 5

以下是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();                                               
}                                                                        

- Let us see.

Answer 6

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

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

- user7130896