来自字符串数组的有效二叉树

Question

我有一个 strings.Each 字符数组，字符串中只能是 r 或 l。我必须检查它是否有效，因为

1. {rlr,l,r,lr, rl}

           *
         /   \
       l       r
        \      /
          r  l
              \
                r
A valid tree as all nodes are present.




2. {ll, r, rl, rr}
         *
        /  \
        -   r
       /    /\
       l    l r

Invalid tree as there is no l node.

根据给定的输入，我必须确定它是否正在创建一个有效的树。我想出了两个解决方案。

1.Using 尝试存储输入并在插入时将每个节点标记为有效或无效。

2.Sort根据长度输入数组。所以对于第一种情况，它将是 { l, r, lr, rl, rlr}
我将创建一组字符串来放置所有输入。如果一个字符串的长度超过 1（对于 rlr :: r, rl），我将考虑其所有从索引 0 开始的前缀并检查 set.if 集合中不存在的任何前缀，然后我将 return 错误。
不知是否有更优的方案或对上述方法进行修改

Answer 1

另一种可能的解决方案是实际构建树（或 trie）并维护一组尚未完成的节点。
如果您完成对列表的迭代并且仍然有不完整的节点，则该树无效。
如果集合为空，则树有效。

例如，在您提供的第二棵树中，对于节点 ll，您还将创建节点 l，但您会将其添加到不完整的集合中。如果后面的节点之一是 l 那么您将从集合中删除它。如果不是，您将以包含您 missing 个节点的非空集结束迭代。

来自字符串数组的有效二叉树

Valid binary tree from array of string

string

algorithm

tree

prefix