具有左右子访问的java节点树遍历

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...should return t = [1,2,4,3,5] and I am getting [].

好吧，让我们看看你用来填充Queue的for循环：

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

你在这里做的是循环，直到queue.poll()返回null，如果我们看javadoc for ^{}，我们看到poll()

Retrieves and removes the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty.

所以，基本上你是在循环，直到你的Queue是空的，然后根据它的大小创建一个数组返回。由于其大小始终为零，因此您总是返回一个长度为零的数组

看起来您正在寻找一个预序遍历，所以您需要做的是使用proper algorithm重写您的方法

如果您致力于非递归遍历，那么here's an algorithm将感谢您以这种方式进行遍历