algorithm - 将一个 BST 转换为在结构上与其他最小插入次数相同的 BST

Question

给定两棵二叉树 T1 和 T2，您必须找到要在 T1 中完成的最少插入次数，以使其在结构上与 T2 相同。如果不可能则返回 -1。

注意事项

1. 假设插入在 BST 中以正常方式完成。
2. 假设在插入时，如果节点v的值等于被插入的值，我们将其插入到节点v的左子树中。
3. 您可以插入任何正整数或负整数。

序列化:对于每个索引i，2*i是左 child ，2*i+1是右 child ，如果没有 child 则为-1

输入 1:

T1:  10 9 20

T2:  5 2 7 1 -1 -1 -1

 10                 5
 /\                / \
9  20             2   7
                 /
                1

如果将 8 插入到 T1 中，它将在结构上与 T2 相同。因此答案是 1。

输入 2:

T1:   10 9 20

T2:   5 -1 7

 10          5
 /\           \
9  20          7

您不能使 T1 和 T2 在结构上完全相同。因此答案是 -1。

我的这段代码在平台上被接受了，但我怀疑它的正确性。我不确定允许插入相等元素的天气是否正确。

我们还需要检查值范围以在树中插入节点吗？

    int Solution::cntMatrix(TreeNode* A, TreeNode* B) {
      if(A==NULL && B==NULL) return 0;
      if(A==NULL) {
          int L=cntMatrix(A,B->left); if(L==-1) return -1;
          int R=cntMatrix(A,B->right);if(R==-1) return -1;
          return L+R+1;
      }
      if(B==NULL) return -1;
      int L=cntMatrix(A->left,B->left);   if(L==-1) return -1;
      int R=cntMatrix(A->right,B->right); if(R==-1) return -1;
      return L+R;
    }

Source : InterviewBit

Answer 1

您可以使用广度优先搜索来解决这个问题。如果 T1 在某一级别的节点数比 T2 多，则比较每个级别的节点数，只需返回 -1否则使用变量 count 并且在每个级别你可以简单地做 count+=(No of nodes of T2 at level N) - (No of nodes of T1 at level N)

然后返回计数就是这样。