java返回一个LinkedList，其中包含AVL树给定范围内的所有元素

Question

我需要编写一个函数，它接受一个AVL节点-root和两个整数：low和high，并返回给定范围内所有元素的链表（低-高包括低和高）。每个树都有.getKey()函数返回键（基本上这就是我们检查范围的内容），还有.getRightChild(), .getLeftChild()和.getData()，这是存储在该节点中的数据

每个节点都有一个键和数据-这是我构建的另一个类“点”，这确实需要说明任何事情（只是为了避免混淆），我们需要返回一个列表，其中包含范围内节点内的所有数据（“点”）

链表是导入的行（java内置util）：
import java.util.LinkedList;

时间复杂度：O(h + k)其中h=height of the tree和k = the elements that reside in the range
不过，O(n)也很棒！（但是log[n] (=h) + k会帮我很多忙）

注意：low和high不一定在树中

输入示例：

并且low = 7, high = 13将返回一个链接列表：[7,9,10,12]

这是我的go（一切都是通用的T）这受到了GeekForGeeks find the number of nodes in the range中这篇文章的严重影响（他们说这是O(h + k)）：

private T[] range(int key1 , int key2) {

    AVLNode<T> common = this.getRoot(); 



    LinkedList<Point> list = new LinkedList<Point>();
    LinkedList<Point> rangeList = wrapperRange(common, key1, key2, list);
    System.out.println(rangeList);
    return null;

}


private LinkedList<Point> wrapperRange(AVLNode<T> root, int low, int high, LinkedList<Point> list) {


    if(root == null)
        return list;

    if(root.getKey() >= low && root.getKey() <= high)
    {
        list.add((Point) root.getData());
        wrapperRange(root.getLeftChild(), low, high, list).addAll(wrapperRange(root.getRightChild(), low, high, list));
        return null;
    }


    else if(root.getKey() < low)
        return this.wrapperRange(root.getRightChild(), low, high, list);
    else
        return this.wrapperRange(root.getLeftChild(), low, high, list);

}

我们使用根高和根低调用range函数，然后调用包装器函数（只是为了跟踪空链表），但是我真的被“添加”元素到列表中的概念所困扰，同时还要创建一个逻辑“基if”（当我们想要返回并退出递归时，我们会得到if）

谢谢你的帮助！非常感谢