이진 트리가 주어지면 모든 절반 노드를 어떻게 제거합니까?

난이도 중급
자주 묻는 질문 수행자 아마존 Microsoft 알레그로 스냅 딜 Synopsys Yahoo
나무조회수 64

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 "이진 트리가 주어 졌을 때 모든 하프 노드를 어떻게 제거합니까?" 이진 트리가 주어 졌음을 나타냅니다. 이제 절반 노드를 제거해야합니다. 하프 노드는 자식이 하나만있는 트리의 노드로 정의됩니다. 왼쪽 자식 또는 오른쪽 자식입니다.

이진 트리가 주어지면 모든 절반 노드를 어떻게 제거합니까?

Inorder Traversal of tree after half nodes removal: 5 3 6 2 7

설명

값이 4 인 노드에는 왼쪽 자식이 하나 있습니다. 따라서 이진 트리에서 제거되고 왼쪽 자식이 트리 위로 이동했습니다. 절반 노드 만 있기 때문입니다. 제거 후, 우리는 inorder traversal이 출력으로 인쇄 된 트리를 남깁니다.

접근

문제는 이진 트리, 모든 하프 노드를 어떻게 제거합니까? 솔루션에 바로 뛰어 들기 전에. 먼저 하프 노드가 무엇인지 알아야합니다. 하프 노드는 단일 자식이있는 이진 트리의 노드입니다. 따라서 자식이 없거나 두 개의 자식이있는 노드는 하프 노드로 간주되지 않습니다. 지금부터 우리는 하프 노드가 무엇인지 알고 있습니다. 우리는 문제에 대한 해결책으로 나아가 야합니다. 해결책은 간단합니다. 우리는 단순히 트리를 횡단하고 하프 노드를 찾을 때마다이를 자식으로 교체합니다. 왼쪽 자식이 존재하고 오른쪽 자식이 null인지 확인합니다. 그런 다음 부모 (또는 절반 노드)를 왼쪽 자식으로 바꿉니다. 마찬가지로, 오른쪽 아이가 유일한 아이라면. 오른쪽 자식이 부모 노드를 대체합니다.

암호

모든 절반 노드를 제거하는 C ++ 코드

#include<bits/stdc++.h>
using namespace std;

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

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

node* removeHalfNode(node* &root){
    if(!root)
        return NULL;
    if(root->left == NULL && root->right != NULL)
        root = removeHalfNode(root->right);
    else if(root->left != NULL && root->right == NULL)
        root = removeHalfNode(root->left);
    else {
        removeHalfNode(root->left);
        removeHalfNode(root->right);
    }
    return root;
}

void inorder(node* root){
    if(root){
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);

  cout<<"Inorder traversal before removing the half nodes"<<endl;
  inorder(root);
  cout<<endl<<"Inorder traversal after removing the half nodes"<<endl;
  root = removeHalfNode(root);
  inorder(root);
}
Inorder traversal before removing the half nodes
9 7 1 6 5 3
Inorder traversal after removing the half nodes
9 7 1 5 3

모든 절반 노드를 제거하는 Java 코드

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static node removeHalfNode(node root){
      if(root == null)
          return null;
      root.left = removeHalfNode(root.left); 
        root.right = removeHalfNode(root.right); 
   
        if(root.left == null && root.right == null) 
            return root;
        if(root.left == null){ 
            node Node = root.right;
            return Node;
        }
        if(root.right == null){ 
            node Node = root.left;
            return Node;
        } 
        return root;
  }

  static void inorder(node root){
      if(root != null){
          inorder(root.left);
          System.out.print(root.data+" ");
          inorder(root.right);
      }
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);

    System.out.println("Inorder traversal before removing the half nodes");
    inorder(root);
    System.out.println("\nInorder traversal after removing the half nodes");
    root = removeHalfNode(root);
    inorder(root);
  }
}
Inorder traversal before removing the half nodes
9 7 1 6 5 3 
Inorder traversal after removing the half nodes
9 7 1 5 3

복잡성 분석

시간 복잡성

의 위에), 바이너리 트리의 모든 노드를 순회했기 때문입니다. 시간 복잡도는 선형입니다.

공간 복잡성

오), 알고리즘은 재귀 알고리즘입니다. 따라서 공간 복잡성은 트리의 높이에 따라 달라지는 컴파일러 스택에 따라 달라집니다.

균열 시스템 설계 인터뷰
Translate »