# 給定一棵二叉樹，如何刪除所有半節點？

## 例

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

## 推薦碼

### 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```