java - 从级别顺序输入创建二叉树

Question

我知道这个问题本身可能是微不足道的，但我正在尝试从级别顺序输入生成一个二叉树，然后遍历它以表示该树已保存在数据结构中。假设输入类似于 - [a,s,e,r,t,*,w] ，它将生成一个二叉树，其表示形式如下 -

                    a
                   / \
                  s   e
                 /\   /\
                r  t *  w

有没有办法实现这个，就像从树输入生成二叉树一样。如果有人以前遇到过此类问题，请分享 JAVA 中的某种实现，例如使用队列。

Answer 1

这是一个粗略的想法，但您可以确切地知道落在给定水平上的范围。

假设当前层包含从 i 到 i+k 的 x 个非*元素，那么下一层将包含从 i+k+1 到 i+k+2x 的 2x 个元素，现在取两个指针，一个在 i 上，另一个在 i 上+k+1 并从左到右为当前层级的每个非 * 元素分配两个 child 。

类似地，对于下一个级别，计算该级别包含多少个元素，即非 * 元素的数量。并重复。