在无组织二叉树中搜索节点?

Question

这是一个概念性问题。我有一个用字符串存储数据的树，但不是按字母顺序存储的。我如何搜索整个树来找到我要找的带字符串的节点。到目前为止，我只能搜索树的一边。

Answer 1

你可以:

1. traverse the tree in any manner, say `DFS` or `BFS`
2. while travering nodes, keep checking the the current node is equivalent to the key string you are searching for.
2.1. compare each character of your search string with each character of current node's value.
2.2. if match found, process your result.
2.3. if not, continue with point 2. 
3. if all the nodes exhausted, you don't have any match. stop the algorithm.

上述算法的复杂度为:

O(N)* O(M) => O(NM)
N - nodes of your tree.
M - length of your node's value + length of your search key's value.

Answer 2

1. 你可以遍历所有树级，并在每个关卡检查所有节点。树的深度相当于迭代次数。
2. 你可以递归地到每个分支，并在找到节点时停止所有迭代(通过使用外部变量或标志)或如果没有子节点。