二分木が与えられた場合、どのようにしてすべてのハーフノードを削除しますか?


難易度 ミディアム
よく聞かれる アコライト Amazon (アマゾン) マイクロソフト PayU Snapdeal シノプシス Yahoo

問題「二分木が与えられた場合、どのようにしてすべてのハーフノードを削除しますか?」 二分木が与えられていると述べています。 次に、ハーフノードを削除する必要があります。 ハーフノードは、子がXNUMXつしかないツリー内のノードとして定義されます。 左の子か右の子のどちらかです。

二分木が与えられた場合、どのようにしてすべてのハーフノードを削除しますか?

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

説明

値4のノードには、左の子がXNUMXつあります。 したがって、それは二分木から削除され、その左の子は二分木の上に移動しました。 半分のノードしかないからです。 削除した後、出力として順序トラバーサルが出力されたツリーが残ります。

アプローチ

問題は与えました 二分木、どのようにしてすべてのハーフノードを削除しますか? ソリューションに飛び込む前に。 まず、ハーフノードとは何かを知る必要がありますか? ハーフノードは、子がXNUMXつあるバイナリツリー内のノードです。 したがって、子がないかXNUMXつの子があるノードは、ハーフノードとは見なされません。 これで、ハーフノードとは何かがわかりました。 問題の解決を進める必要があります。 解決策は簡単です。 ツリーをトラバースするだけで、ハーフノードが見つかるたびにその子に置き換えます。 左の子が存在し、右の子が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

複雑さの分析

時間の複雑さ

オン)、 二分木のすべてのノードをトラバースしたからです。 時間計算量は線形です。

スペースの複雑さ

ああ)、 アルゴリズムは再帰的アルゴリズムです。 したがって、スペースの複雑さはコンパイラスタックに依存し、コンパイラスタックはツリーの高さに依存します。