給定一棵二叉樹,如何刪除所有半節點?  


難度級別 中烘焙
經常問 ol石 亞馬遜 Microsoft微軟 PayU Snapdeal 新思 雅虎

問題“給出一棵二叉樹,如何刪除所有半節點?” 指出您已獲得一棵二叉樹。 現在,您需要刪除半節點。 半節點定義為樹中只有一個子節點的節點。 是左子還是右子。

例  

給定一棵二叉樹,如何刪除所有半節點?

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

解釋

值為4的節點有一個左子節點。 因此,它已從二叉樹中刪除,它的左子樹已在樹上向上移動。 因為只有一半的節點。 刪除後,我們剩下一棵樹,其有序遍歷已作為輸出打印出來。

途徑  

問題給了 二叉樹,如何刪除所有半節點? 在跳入解決方案之前。 我們首先應該知道什麼是半節點? 半節點是二叉樹中具有單個子節點的節點。 因此,沒有子節點或有兩個子節點的節點將不被視為半節點。 從現在開始,我們知道什麼是半節點。 我們應該繼續解決問題。 解決方案很簡單。 我們只需要遍歷樹,只要找到一個半節點,我們就用它的子節點替換它。 我們檢查左子級是否存在,右子級是否為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

複雜度分析  

時間複雜度

上), 因為我們遍歷了二叉樹中的所有節點。 時間複雜度是線性的。

也可以看看
連續數組

空間複雜度

哦), 該算法是遞歸算法。 因此,空間複雜度取決於編譯器堆棧,而編譯器堆棧又取決於樹的高度。