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

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

信息技术应该返回t=[1,2,4,3,5]，我得到[]。

好吧，让我们看看您用来填充队列的for循环：

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

这里所做的是循环，直到queue.poll（）返回null，如果我们查看ArrayDeque的javadoc，我们会看到投票（）

检索并删除此deque表示的队列的头部（换句话说，此deque的第一个元素），或者如果此deque为空，则返回null。

所以，基本上你是在循环，直到你的队列是空的，然后根据它的大小创建一个数组来返回。因为它的大小总是零，所以你总是返回一个零长度的数组。

看起来你要做一个预序遍历，所以你需要做的是用一个合适的算法重写你的方法。

如果你致力于非递归遍历，这里有一个算法可以实现。