从父数组测试用例失败构造二叉树

Question

题目的

Link-[Link][1]

基本上我们得到了一个整数数组及其大小。问题是从中构造一棵二叉树。每个索引对应一个节点中存储的数据，该索引的值就是父节点的数据。根节点索引的值将始终为 -1，因为根没有父节点。输出将是树的排序级别顺序遍历。

现在我的方法是从 1 到 n（不是第 0 个 element/root 节点）解析数组，对于每个元素，我使用第一个函数获取它的父元素，并相应地插入子元素。但是一个特定的测试用例失败了。也许网站自己的输出不正确。我将 post 以下所有内容：-

示例测试用例-

array-7 的大小

元素- -1 0 0 1 1 3 5

输出- 0 1 2 3 4 5 6

特定测试用例（这是我的疑问）-

数组大小 - 42

元素- 3 19 1 41 35 29 27 11 17 23 9 15 33 13 39 23 19 25 21 1 33 15 31 21 5 7 37 29 7 11 31 39 -1 27 3 9 25 17 13 41 37 35

网站的输出 - 32

我的输出 - 0

函数


void getParent(Node* root, int val, Node* &main)
{
    if(root==NULL) return;
    if(root->data==val){
        main=root;
        return;
    }
    getParent(root->left,val,main);
    getParent(root->right,val,main);
    
}

Node *createTree(int parent[], int n)
{
    if(n==0) return NULL;
    Node * root=new Node(0);
    for(int i=1;i<n;i++)
    {
        Node* main=NULL;
        getParent(root,parent[i],main);
        //main has the parent
        
        Node* child=new Node(i);
        if(main==NULL) break;
        
        
        if(main->left==NULL)
        {
            main->left=child;
        }
        else if(main->right==NULL)
        {
            main->right=child;
        }
    }
    return root;
} 


  [1]: https://www.geeksforgeeks.org/construct-a-binary-tree-from-parent-array-representation/
  [2]: https://i.stack.imgur.com/0fRmn.png

Answer 1

不确定您使用 getParent 方法做什么。此外，您正在启动一个值为 0 的根节点，而不是在循环中对其进行任何处理，最后您 return 根节点。我怀疑你的根总是有一个值 0.

其实解决方法很简单。您使用每个节点的值作为数组的索引来初始化一个节点数组。例如，对于大小为 5 的数组，您创建了一个包含 5 个节点的数组，每个节点都具有其所在索引的值。

然后下一步是遍历 parent 数组并查看位于 parent[i] 的节点是否具有 left 或 right “可用”，如果是则分配相应的节点。

密码是：

Node* createTree(int parent[], int n) {
  Node** nodes = new Node*[n];
  for ( int i = 0; i < n; i++ )
      nodes[i] = new Node(i);
  int rootIndex = 0;
  for ( int i  = 0; i < n; i++ ) {
    if ( parent[i] == -1 ) {
      rootIndex = i;
    } else {
      if ( nodes[parent[i]] -> left == NULL ) {
        nodes[parent[i]] -> left = nodes[i];
      } else if ( nodes[parent[i]] -> right == NULL ) {
          nodes[parent[i]] -> right = nodes[i];
      }
    }
    
  }
  return nodes[rootIndex];
}

从父数组测试用例失败构造二叉树

Construct Binary Tree from Parent Array test case failing

c++

algorithm

binary-tree

data-structures