使用二进制搜索树inOrder中的数据填充列表

Question

我希望将二叉树的值按顺序存储在列表中。我有一个调用helper方法的公共方法，但是当我打印返回的列表时，我总是得到一个空列表……

public List inOrderList(){
    return inOrderList(overallRoot);   //root value
}

private List inOrderList(SearchTreeNode root){
    List<E> list1 = new ArrayList<E>();    //new list (will be returned)
    if(root==null){
        return list1;     //returns empty list
    }
     //List is NOT empty, let's do this thing.
    else {
        //create a new list, that calls left method recursive on left node
        List<E> podo = inOrderList(root.left);
        //Here, I *believe* we've reached the bottom. Add every podo to list1   
        list1.addAll(podo);

        //do the same thing for the right tree
        List<E> dopo = inOrderList(root.right);
        list1.addAll(dopo);        
   }

    //return the list we just filled from our BST
    return list1;
}

我选择不尝试单独用数据填充我的列表。我认为使用addAll并以这种方式存储所有内容会是一个更好的选择。鉴于此解决方案不起作用，我也尝试了存储数据。

private List<Integer> inOrderList(IntTreeNode root){
    List<Integer> list1 = new ArrayList<Integer>();
    if(root==null){
        return list1;
    } else { 
        while(root!=null){
            List<Integer> podo = inOrderList(root.left);
            list1.add(root.data);
            List<Integer> dopo = inOrderList(root.right);
            list1.add(root.data);
        }
   
    }
    return list1;
}

我发现这至少填满了列表，但是它只是简单地插入了两次根值，然后就完成了。我已经为此工作了大约一个小时，似乎想不出更好的办法，所以我想我应该求助于你们。

我哪里做错了/我该怎么做？

Answer 1

在伪代码中，您的函数将如下所示。我建议您尝试使用调试器，并检查它在较小的输入上的工作情况。

private void inOrder(Node node, List<Integer> list) {
  if (node == null) {
    return;
  }
  inOrder(node.left, list);
  list.add(node.data);
  inOrderList(node.right, list);
}

Answer 2

我意识到我正在以错误的方式来处理它。

解决方案：

public List<E> inOrderList() {
List<E> list = new ArrayList<E>();
inOrderList(overallRoot, list);
return list;

}
//helper method
private void inOrderList(SearchTreeNode root, List<E> list) {
if(root == null)
    return;       
inOrderList(root.left, list);
list.add((E)root.data);
inOrderList(root.right, list);

}