克隆具有随机指针的二叉树


难度级别
经常问 ol石 亚马逊 思科 事实集 狂徒 谷歌 微软 操作 Snapchat
哈希

问题陈述

您会得到一个完整的 二叉树 与一些随机指针。 随机指针指向的是每个节点指向其左,右子节点之外的节点。 因此,这也改变了简单的二叉树中节点的标准结构。 现在,二叉树的节点将把数据存储在当前节点,并指向左,右和随机指针。 因此,现在我们很好地解决了这个问题甚至提出了什么? 问题“使用随机指针克隆二叉树”要求创建一个新的二叉树,它是给定初始树的精确副本。 因此,在新创建的树中,如果我们选择一个节点,则其左,右和随机指针将指向该新树中与原始树中的节点相对应的节点。

使用案列

输入

克隆具有随机指针的二叉树

Inorder traversal of original binary tree is [current node data, random pointer data]:
[1 2], [2 7], [3 9], [5 1], [7 1], [9 5],

Inorder traversal of cloned binary tree is[current node data, random pointer data]:
[1 2], [2 7], [3 9], [5 1], [7 1], [9 5],

说明

二叉树的左侧和右侧节点在每个节点的左侧和右侧照常显示。 并且除左,右指针外的所有指针都是随机指针。 一些边缘具有双箭头(指向两个方向)。 指向该节点的任何父节点的方向表示该节点具有指向父节点的随机指针。 输出以[当前节点数据/随机节点数据]格式给出。

散列方法

因此,我们知道我们需要创建一棵新树,它是初始树的精确副本。 我们可以进行有序遍历并构造一个副本。 但是我们将面临随机指针的问题,因为某些节点可能指向尚未构造的节点。 所以要摆脱这个错误。 我们将首先构建一棵新树。 然后用 哈希图 它存储与原始树中每个节点相对应的新节点的地址。 因此,我们再次运行有序遍历,并使随机指针指向新树的节点(这些节点作为值存储在HashMap中)。

高效方法

在上述方法中,我们必须保持 哈希图 它存储了与原始树中每个节点相对应的克隆节点地址。 因此,除了执行此操作外,我们将执行克隆克隆操作。 链表 与随机指针。 我们将新创建的节点推入左子节点与原始树中的相应节点之间。 因此,到目前为止,我们已经更改了初始树的结构。 要设置随机指针,我们知道与一个节点相对应的新节点始终是其左子节点。 因此,我们只需将随机指针设置为输入树中节点的左子节点即可。 但是,我们仍然需要照顾一件事。 我们需要恢复初始树和克隆树节点的左子节点。 一旦完成,我们就克隆了带有随机指针的二叉树。

代码

C ++代码克隆具有随机指针的二叉树

#include <iostream>
using namespace std;

struct node{
    int data;
  node *left, *right, *random;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = tmp->random = NULL;
}

// print inorder traversal of the given tree in [node, random node] format
void inorder(node* root)
{
  if(root == NULL)
    return;
  // print inorder traversal of left tree
  inorder(root->left);
  // print in [current node, random node] format
  cout << "[" << root->data << " ";
  if (root->random == NULL)
    cout << "NULL], ";
  else
    cout << root->random->data << "], ";
  // print inorder traversal of right tree
  inorder(root->right);
}

// insert clone nodes between the original node and its left child
node* insertCloneNode(node* originalNode)
{
  if (originalNode == NULL)
    return NULL;

  node* left = originalNode->left;
  originalNode->left = create(originalNode->data);
  originalNode->left->left = left;
  if(left != NULL)
    left->left = insertCloneNode(left);

  originalNode->left->right = insertCloneNode(originalNode->right);
  return originalNode->left;
}

// sets the random pointers in clone tree
void setRandomNode(node* originalNode, node* cloneNode)
{
  if (originalNode == NULL)
    return;
  if(originalNode->random != NULL)
    cloneNode->random = originalNode->random->left;
  else
    cloneNode->random = NULL;

  if(originalNode->left != NULL && cloneNode->left != NULL)
    setRandomNode(originalNode->left->left, cloneNode->left->left);
  setRandomNode(originalNode->right, cloneNode->right);
}

// after all the work restore the left pointers in original and clone tree
void restoreTreeLeftNode(node* originalNode, node* cloneNode)
{
  if (originalNode == NULL)
    return;
  if (cloneNode->left != NULL)
  {
    node* cloneLeft = cloneNode->left->left;
    originalNode->left = originalNode->left->left;
    cloneNode->left = cloneLeft;
  }
  else
    originalNode->left = NULL;

  restoreTreeLeftNode(originalNode->left, cloneNode->left);
  restoreTreeLeftNode(originalNode->right, cloneNode->right);
}

// constructs the new clone tree
node* cloneTree(node* originalNode)
{
  if (originalNode == NULL)
    return NULL;
  node* cloneNode = insertCloneNode(originalNode);
  setRandomNode(originalNode, cloneNode);
  restoreTreeLeftNode(originalNode, cloneNode);
  return cloneNode;
}


int main()
{
  node *root = create(3);
  node* two = create(2);
  node* one = create(1);
  node* seven = create(7);
  node* five = create(5);
  node* nine = create(9);

  root->left = two;
  root->left->left = one;
  root->right = seven;
  root->right->left = five;
  root->right ->right = nine;

  root->random = nine;
  root->left->random = seven;
  root->left->left->random = two;
  root->right->random = one;
  root->right->left->random = one;
  root->right->right->random = five;

  cout << "Inorder traversal of original binary tree is [current node data, random pointer data]: \n";
  inorder(root);

  node *clone = cloneTree(root);

  cout << "\n\nInorder traversal of cloned binary tree is[current node data, random pointer data]: \n";
  inorder(clone);

  return 0;
}
Inorder traversal of original binary tree is [current node data, random pointer data]:
[1 2], [2 7], [3 9], [5 1], [7 1], [9 5],

Inorder traversal of cloned binary tree is[current node data, random pointer data]:
[1 2], [2 7], [3 9], [5 1], [7 1], [9 5],

Java代码克隆具有随机指针的二叉树

import java.util.*;
// Class that denotes a node of the tree
class node
{ 
    int data; 
    node left, right, random; 
 
    public node(int data) 
    { 
        this.data = data;
        left = right = random = null; 
    } 
}
 
class Tree 
{ 
    static node root;
  static node create(int data) {
    node tmp = new node(data);
    return tmp;
  }
  // print inorder traversal of the given tree in [node, random node] format
  static void inorder(node root){
    if(root != null){
      // print inorder traversal of left tree
      inorder(root.left);
      // print in [current node, random node] format
      System.out.print("[" + root.data + " ");
      if(root.random == null)
        System.out.print("null], ");
      else
        System.out.print(root.random.data +"], ");
      // print inorder traversal of right tree
      inorder(root.right);
    }
  }
 
  // insert clone nodes between the original node and its left child
  static node insertCloneNode(node originalNode) 
  { 
    if (originalNode == null) 
      return null; 
 
    node left = originalNode.left; 
    originalNode.left = create(originalNode.data); 
    originalNode.left.left = left; 
    if(left != null) 
      left.left = insertCloneNode(left); 
 
    originalNode.left.right = insertCloneNode(originalNode.right); 
    return originalNode.left; 
  } 
 
  // sets the random pointers in clone tree
  static void setRandomNode(node originalNode, node cloneNode) 
  { 
    if (originalNode != null){
      if(originalNode.random != null) 
        cloneNode.random = originalNode.random.left; 
      else
        cloneNode.random = null; 
 
      if(originalNode.left != null && cloneNode.left != null) 
        setRandomNode(originalNode.left.left, cloneNode.left.left); 
      setRandomNode(originalNode.right, cloneNode.right); 
    }
  } 
 
  // after all the work restore the left pointers in original and clone tree
  static void restoreTreeLeftNode(node originalNode, node cloneNode) 
  { 
    if (originalNode != null) {
      if (cloneNode.left != null) 
      { 
        node cloneLeft = cloneNode.left.left; 
        originalNode.left = originalNode.left.left; 
        cloneNode.left = cloneLeft; 
      } 
      else
        originalNode.left = null; 
 
      restoreTreeLeftNode(originalNode.left, cloneNode.left); 
      restoreTreeLeftNode(originalNode.right, cloneNode.right); 
    }
  } 
 
  // constructs the new clone tree
  static node cloneTree(node originalNode) 
  { 
    if (originalNode == null)
      return null;
    node cloneNode = insertCloneNode(originalNode); 
    setRandomNode(originalNode, cloneNode); 
    restoreTreeLeftNode(originalNode, cloneNode); 
    return cloneNode; 
  } 
 
  public static void main(String[] args) {
    node root = create(3);
    node two = create(2);
    node one = create(1);
    node seven = create(7);
    node five = create(5);
    node nine = create(9);
 
    root.left = two;
    root.left.left = one;
    root.right = seven;
    root.right.left = five;
    root.right .right = nine;
 
    root.random = nine;
    root.left.random = seven;
    root.left.left.random = two;
    root.right.random = one;
    root.right.left.random = one;
    root.right.right.random = five;
 
    System.out.print("Inorder traversal of original binary tree is[current node data, random pointer data]: \n");
    inorder(root);
 
    node clone = cloneTree(root);
 
    System.out.print("\n\nInorder traversal of cloned binary tree is[current node data, random pointer data]: \n");
    inorder(clone);
  }
}
Inorder traversal of original binary tree is[current node data, random pointer data]: 
[1 2], [2 7], [3 9], [5 1], [7 1], [9 5], 

Inorder traversal of cloned binary tree is[current node data, random pointer data]: 
[1 2], [2 7], [3 9], [5 1], [7 1], [9 5],

克隆具有随机指针的二叉树的复杂度分析

时间复杂度 

上), 我们刚刚遍历了二叉树中的节点,并且由于二叉树中有N个节点。 因此,时间复杂度是线性的。

空间复杂度

O(1), 因为我们还没有在数组或映射中存储任何信息。 因此,空间复杂度是恒定的。