节点树遍历左右儿童访问

Question

试图穿越树并为我的数组获得空值。我需要穿越树，该树只允许访问节点类别的类定义中的左右儿童。

class Tree<T> {
 Tree(T x) {
   value = x;
 }
 T value;
 Tree<T> left;
 Tree<T> right;
}
public int[] traverseTree(Tree<Integer> t) {
   Stack<Tree<Integer>> stack = new Stack<Tree<Integer>>();
    Tree<Integer> node = root;
    while (node != null) { 
        stack.push(node);
        node = node.left;
    }
    int[] result = new int[stack.size()];
    int i = 0;
    while (stack.size() > 0) {
        node = stack.pop();
        if(node != null) {
            result[i] = node.value;
            i++;
        }
        if (node.right != null) {
            node = node.right;
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }
    }
    return result;
}

它采用

的输入

t = {
"value": 1,
"left": {
    "value": 2,
    "left": null,
    "right": {
        "value": 3,
        "left": null,
        "right": null
    }
},
"right": {
    "value": 4,
    "left": {
        "value": 5,
        "left": null,
        "right": null
    },
    "right": null
   }
 }

这应该返回[1,2,4,3,5]，我得到了[]。我也尝试过像

这样的循环

 if(root != null) {
     queue.add(root);
  }
 while(root.left != null) {
   while(root.right != null) {
      queue.add(root);
      root = root.right;
   }
   queue.add(root);
   root = root.left;
}

这也行不通。这也会给我一个[]数组。遍历应在树高度指示的树级别（这是水平）的树级别上从左到右打印树。有任何想法吗？

Answer 1

it ...应该返回t = [1,2,4,3,5]，我得到[]。

好吧，让我们看一下您用来填充Queue的前循环：

for (Tree<Integer> node = root; node != null; node = queue.poll()) {
    //stuff
}

您在这里做的是循环直到queue.poll()返回null，如果我们查看ArrayDeque的Javadoc，我们会看到poll()

检索和删除该deque代表的队列的头（换句话说，此Deque的第一个元素）或如果此Deque为空，则返回NULL。

因此，基本上您要循环直到Queue为空，然后根据其大小返回的数组创建数组。由于其大小始终为零，因此您始终返回零长度数组。

看起来您要进行预订的遍历，因此您需要做的就是使用适当的算法重写方法。

如果您致力于非恢复遍历，这是这样做的算法。