Java

Question

我正在尝试编写代码将二叉树转换为具有相同深度的节点列表。如果一棵树的深度为 d，则将创建 d 个列表。逻辑是中序遍历，将当前遍历的节点加入到合适深度的链表中。

public void treeToListofNodesByLevel(Node<T> n,int depth, ArrayList<LinkedList<Node<T>>> treeList){

        if(n.right != null){
            inOrderWithHeight(n.right, depth + 1);
        }
        if(treeList.size() >= depth){
            treeList.add(depth, new LinkedList<Node<T>>() );
        }
        treeList.get(depth).add(n);
        if(n.left != null){
            inOrderWithHeight(n.left, depth + 1);
        }

    }

然后调用：

ArrayList<LinkedList<Node<T>>> result = new ArrayList<LinkedList<Node<T>>>();
treeToListofNodesByLevel(root, 0, result);

这行得通吗？有没有我没有处理的极端情况？另外，现在我正在传递要由方法返回的列表列表，因为我想不出一种方法来在方法中初始化它并在结束时返回它，同时还保持递归结构。有更好的方法吗？

Answer 1

我无法理解 "inOrderWithHeight" 方法的作用。我为这个问题所做的（未优化）是使用两个队列像 BFS 一样遍历，并在每次迭代中将该深度的节点添加到该迭代的列表中（每次迭代都遍历树的一个深度）。这是我为二叉树执行此操作的代码，正如您在答案中所假设的那样：

Queue<Node<T>> queue1 = new LinkedList<Node<T>>() ;
Queue<Node<T>> queue2 = new LinkedList<Node<T>>() ;
public void treeToListofNodesByLevel(Node<T> root, ArrayList<LinkedList<Node<T>>> treeList) {
    if (root == null)
        return;
    int curr_depth = 0;
    queue1.add(root);
    while(!queue1.isEmpty()){
        treeList.add(curr_depth, new LinkedList<Node<T>>());
        while(!queue1.isEmpty()){
            Node<T> node = queue1.remove();
            treeList.get(curr_depth).add(node);
            if(node.left != null) queue2.add(node.left);
            if(node.right != null) queue2.add(node.right);
        }
        curr_depth++;
        while(!queue2.isEmpty()){
            Node<T> node = queue2.remove();
            queue1.add(node);
        }    
    }
}

我是在没有语法检查的情况下临时写的，可能有编译器错误。但希望你明白了。

Answer 2

您的总体概念非常完美。它会起作用，并且应该处理所有情况。

但是，您在细节上有一些错误：

您检查何时添加新列表的比较方向错误。应该是 if (treeList.size() <= depth).
对 inOrderWithHeight() 的每次调用（您尚未提供任何代码）都应该是对 treeToListofNodesByLevel() 的递归调用。保持前两个参数不变，只为第三个参数传递 treeList。
这更多是一个风格问题，但参数类型通常应声明为满足您实际需要的最高级别类型。这里不需要指定 ArrayList 或 LinkedList，任何 List 都可以。将 treeList 参数的类型更改为 List<List<Node<T>>>.

对于在方法内初始化列表同时还使用递归的问题，这就是实现辅助方法的目的。获取 treeToListofNodesByLevel 的当前主体并将其移动到私有方法中（递归调用已更改，因此私有方法会调用自身），我们将其命名为 treeToListofNodesByLevelHelper。然后把现在的public方法改成这样：

public List<List<Node<T>>> treeToListofNodesByLevel(Node<T> node) {
    List<List<Node<T>>> result = new ArrayList<>();
    treeToListofNodesByLevelHelper(node, 0, result);
    return result;
}

Answer 3

为什么只用同样的功能代码会更漂亮:

    public void treeToListofNodesByLevel(BinaryTree node, int currentDepth, List<List<BinaryTree>> result){

    // Check if the list for the currentDepth is created
    if(result.get(currentDepth) != null){
        result.add(currentDepth, new ArrayList<BinaryTree>())
    }

    // Add the current node to the list
    result.get(currentDepth).add(node);


    // Recursive the left node
    if(node.left != null){
        treeToListofNodesByLevel(node.left, currentDepth+1, result);
    } 

    // Recursive the right node
    if(node.right != null){
        treeToListofNodesByLevel(node.right, currentDepth+1, result);
    }
}

在你的主函数中：

List<List<BinaryTree>> result = new ArrayList<>();
BinaryTree root = new BinaryTree();  
treeToListofNodesByLevel(root, 0, result);

Java - 将树转换为具有相同深度的节点列表

Java - Convert a Tree to a Lists of Nodes with same depth

binary-tree