代码之家 › 专栏 › 技术社区 › ismael oliva

如何将节点树的数据转换为有序的ArrayList?

binary tree recursion java

ismael oliva · 技术社区 · 6 年前

public class Node {
private int data;

public int getData() {
    return data;
}

private Node left;
private Node right;

public Node(int d, Node l, Node r) {
    data = d;
    left = l;
    right = r;
}

// Deep copy constructor
public Node(Node o) {
    if (o == null) return;
    this.data = o.data;
    if (o.left != null) this.left = new Node(o.left);
    if (o.right != null) this.right = new Node(o.right);
}

public List<Integer> toList() {
// Recursive code here that returns an ordered list of the nodes
}

全班在此: https://pastebin.com/nHwXMVrd

我可以使用什么递归解决方案来返回节点内整数的有序ArrayList?我尝试了很多方法,但我一直很难找到递归解决方案。

2 回复 | 直到 6 年前

Schidu Luca 6 年前

考虑到你有 bst 您可以在中进行顺序遍历,这将为您提供所有元素的递增顺序(排序),这是一个如何完成的示例:

 public List<Integer> toList() {
        return createOrderedList(this);
 }

 private List<Integer> createOrderedList(Node root) {
     if(root == null) {
         return new ArrayList<>();
     }

     List<Integer> list = new ArrayList<>();
     list.addAll(createOrderedList(root.left));
     list.add(root.data);
     list.addAll(createOrderedList(root.right));

     return list;
 }

Robert 6 年前

我对Java并不精通,但这将是做这件事的总体思路:

public List<Integer> toList() 
{
   List<Integer> newList = new List<Integer>();
   newList.add(this.data);
   if(left != null)
      newList.addAll(left.toList());
   if(right != null)
      newList.addAll(right.toList());
   return newList;
}

推荐文章

jkfe · 为什么println会在这段递归代码中执行?

2 年前

Brian Patterson · Javascript自定义数组。原型方法日志“未定义”

2 年前

Jimmy · 这种算法怎么能按顺序遍历树“爬上”树呢?

2 年前

iRon · 匿名递归函数

2 年前

ProgrammingNoob321312 · 为什么这个Java代码会输出“3210123”?

2 年前

AvirukBasak · gcc中无return语句的尾部递归

2 年前

Dharmik Patel · 使用python递归完全可以整除

2 年前

W.tan · 一维最短距离递归算法

2 年前

ncarrawa · 将1添加到i(递归)时出现类型错误

2 年前

Eren · Python递归何时返回[duplicate]

2 年前