获取二叉树特定级别的所有节点

Question

我有一个 BinaryTree，我想获取特定级别的所有节点。顺序无关紧要。我想尝试用 recursion 来做到这一点。我的方法如下所示：

public List<T> getNodesOnLevel(int i){
    int recursionTool = i
    //to do
    recursionTool-=1
    }

我尝试 while(recursionTool != 0){ 方法.... 然后是 recursionTool -1} 但我最终让所有节点 until 达到了想要的水平。我的节点看起来像这样：

class Node<T>{
    T val;
    Node<T> left;
    Node<T> right;
    Node(T v){
        val = v;
        left = null;
        right = null;
    }

Answer 1

这可能对您有所帮助。我曾将此方法用于打印节点，但您可以更改它。

public void printGivenLevel(TNode root, int level) {
    if (root == null)
        return;
    if (level == 1 && root.getValue() != null) {
   //  here,  add  root.getValue() to list
    } else if (level > 1) {
        printGivenLevel(root.getLeft(), level - 1);
        printGivenLevel(root.getRight(), level - 1);
    }
}

Answer 2

通过连接递归调用返回的列表，可以将其实现为纯函数算法。不幸的是，这在 Java 中效率很低，因为所有检索到的值都在每个递归级别通过列表创建或连接复制一次。

如果您愿意使用突变，这里有一个避免复制的解决方案（假设 this 是 Node<T>）：

private void getNodesOnLevel(int level, List<T> list) {
    if (node == null) return;
    if (level == 0) {
        list.add(this.val);
    } else {
        this.left.getNodesOnLevel(level - 1, list);
        this.right.getNodesOnLevel(level - 1, list);
    }
}

上面的方法需要用一个空的（可变的）列表作为第二个参数来调用，所以我们需要另一个方法：

public List<T> getNodesOnLevel(int level) {
    List<T> list = new ArrayList<>();
    this.getNodesOnLevel(level, list);
    return list;
}

（在复杂性方面，纯函数解决方案是 O(LN)，其中 L 是级别，N 是该级别的节点数。我的解决方案是 O(N)。由于 ArrayList.append 实现列表大小调整的方式，列表中的每个值平均将被复制两次。通过使用容量为 2level.)

获取二叉树特定级别的所有节点

Get all nodes of a specific level of a Binary Tree

java

recursion

binary-tree