给定一棵二叉树,如何删除所有半节点?


难度级别 中等
经常问 ol石 亚马逊 微软 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

复杂度分析

时间复杂度

上), 因为我们遍历了二叉树中的所有节点。 时间复杂度是线性的。

空间复杂度

哦), 该算法是递归算法。 因此,空间复杂度取决于编译器堆栈,而编译器堆栈又取决于树的高度。