algorithm - 二 fork 树检测 - 为什么要比较 2 个遍历

Question

1. 为什么我们需要比较中序遍历字符串和前序遍历字符串来确定树是否是更大树的子树？为什么1个遍历字符串不够用？
2. 我们可以用后序遍历字符串替换上面的字符串之一吗？

假设:

1. 我有一个不平衡的二叉树。这不一定是二叉搜索树。
2. 可以使用给定的 compareTO() 方法比较内部节点和叶子的数据
3. 树很大，因此不可能使用后缀树。假设正常递归是可能的。

Answer 1

Ad1. 假设您有更大的树:

     5
   /
  6     <something>
 / \
7   3
   /       
  2 

现在请注意，以节点 6 为根的子树的中序遍历将为 [7,6,2,3]。现在告诉我以下树的中序遍历是什么:

  6
 / \
7   2
     \      
      3

您猜对了:[7,6,2,3]。中序遍历在一般情况下描述的不是单个二叉树，而是多个二叉树。如果这是一棵二叉搜索树，那么您只需要 1 个前序或后序遍历，因为中序遍历将始终相同(所有节点都按排序顺序)。

Ad2.您可以使用中序和前序或后序遍历重建一棵树。在一般情况下，您不能重建具有前序和后序遍历的树，可能有多个选项。唯一可以做到这一点的情况是完整的二叉树(每个节点，叶子除外，必须有 2 个子节点)。