原文：

给定二叉树和由要删除的节点值组成的数组arr[]，任务是打印 删除节点后的中的一个。

示例：

输入：arr[] = {10, 5}

``` 10 / \ 20 30 / \ \ 4 5 7

```

输出：

4 20 30 7

输入：arr[] = {5}

``` 1 / \ 5 6 / \ 10 12

```

输出：

10 1 6 12

方法：请按照以下步骤解决问题：

  1. 执行二叉树的。
  2. 对于每个节点，检查它是否包含要删除的值。
  3. 如果发现是真的，则将其子级存储为森林的根。 通过打印森林。

下面是上述方法的实现：

c 

// c   program to implement 
// the above approach 
#include  
using namespace std; 
// stores the nodes to be deleted 
unordered_map mp; 
// structure of a tree node 
struct node { 
    int key; 
    struct node *left, *right; 
}; 
// function to create a new node 
node* newnode(int key) 
{ 
    node* temp = new node; 
    temp->key = key; 
    temp->left = temp->right = null; 
    return (temp); 
} 
// function to check whether the node 
// needs to be deleted or not 
bool deletenode(int nodeval) 
{ 
    return mp.find(nodeval) != mp.end(); 
} 
// function to perform tree pruning 
// by performing post order traversal 
node* treepruning(node* root, vector& result) 
{ 
    if (root == null) 
        return null; 
    root->left = treepruning(root->left, result); 
    root->right = treepruning(root->right, result); 
    // if the node needs to be deleted 
    if (deletenode(root->key)) { 
        // store the its subtree 
        if (root->left) { 
            result.push_back(root->left); 
        } 
        if (root->right) { 
            result.push_back(root->right); 
        } 
        return null; 
    } 
    return root; 
} 
// perform inorder traversal 
void printinordertree(node* root) 
{ 
    if (root == null) 
        return; 
    printinordertree(root->left); 
    cout << root->key << " "; 
    printinordertree(root->right); 
} 
// function to print the forests 
void printforests(node* root, int arr[], int n) 
{ 
    for (int i = 0; i < n; i  ) { 
        mp[arr[i]] = true; 
    } 
    // stores the remaining nodes 
    vector result; 
    if (treepruning(root, result)) 
        result.push_back(root); 
    // print the inorder traversal of forests 
    for (int i = 0; i < result.size(); i  ) { 
        printinordertree(result[i]); 
        cout << endl; 
    } 
} 
// driver code 
int main() 
{ 
    node* root = newnode(1); 
    root->left = newnode(12); 
    root->right = newnode(13); 
    root->right->left = newnode(14); 
    root->right->right = newnode(15); 
    root->right->left->left = newnode(21); 
    root->right->left->right = newnode(22); 
    root->right->right->left = newnode(23); 
    root->right->right->right = newnode(24); 
    int arr[] = { 14, 23, 1 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    printforests(root, arr, n); 
}

java

// java program to implement 
// the above approach 
import java.util.*; 
class gfg{ 
// stores the nodes to be deleted 
static hashmap mp  = new hashmap<>(); 
// structure of a tree node 
static class node 
{ 
    int key; 
    node left, right; 
}; 
// function to create a new node 
static node newnode(int key) 
{ 
    node temp = new node(); 
    temp.key = key; 
    temp.left = temp.right = null; 
    return (temp); 
} 
// function to check whether the node 
// needs to be deleted or not 
static boolean deletenode(int nodeval) 
{ 
    return mp.containskey(nodeval); 
} 
// function to perform tree pruning 
// by performing post order traversal 
static node treepruning(node root,  
                        vector result) 
{ 
    if (root == null) 
        return null; 
    root.left = treepruning(root.left, result); 
    root.right = treepruning(root.right, result); 
    // if the node needs to be deleted 
    if (deletenode(root.key))  
    { 
        // store the its subtree 
        if (root.left != null)  
        { 
            result.add(root.left); 
        } 
        if (root.right != null) 
        { 
            result.add(root.right); 
        } 
        return null; 
    } 
    return root; 
} 
// perform inorder traversal 
static void printinordertree(node root) 
{ 
    if (root == null) 
        return; 
    printinordertree(root.left); 
    system.out.print(root.key   " "); 
    printinordertree(root.right); 
} 
// function to print the forests 
static void printforests(node root,  
                         int arr[], int n) 
{ 
    for (int i = 0; i < n; i  ) 
    { 
        mp.put(arr[i], true); 
    } 
    // stores the remaining nodes 
    vector result  = new vector<>(); 
    if (treepruning(root, result) != null) 
        result.add(root); 
    // print the inorder traversal of forests 
    for (int i = 0; i < result.size(); i  )  
    { 
        printinordertree(result.get(i)); 
        system.out.println(); 
    } 
} 
// driver code 
public static void main(string[] args) 
{ 
    node root = newnode(1); 
    root.left = newnode(12); 
    root.right = newnode(13); 
    root.right.left = newnode(14); 
    root.right.right = newnode(15); 
    root.right.left.left = newnode(21); 
    root.right.left.right = newnode(22); 
    root.right.right.left = newnode(23); 
    root.right.right.right = newnode(24); 
    int arr[] = { 14, 23, 1 }; 
    int n = arr.length; 
    printforests(root, arr, n); 
} 
} 
// this code is contributed by rajput-ji

c

// c# program to implement 
// the above approach 
using system; 
using system.collections.generic; 
class gfg{ 
// stores the nodes to be deleted 
static dictionary mp = new dictionary(); 
// structure of a tree node 
class node 
{ 
    public int key; 
    public node left, right; 
}; 
// function to create a new node 
static node newnode(int key) 
{ 
    node temp = new node(); 
    temp.key = key; 
    temp.left = temp.right = null; 
    return (temp); 
} 
// function to check whether the node 
// needs to be deleted or not 
static bool deletenode(int nodeval) 
{ 
    return mp.containskey(nodeval); 
} 
// function to perform tree pruning 
// by performing post order traversal 
static node treepruning(node root,  
                        list result) 
{ 
    if (root == null) 
        return null; 
    root.left = treepruning(root.left, result); 
    root.right = treepruning(root.right, result); 
    // if the node needs to be deleted 
    if (deletenode(root.key))  
    { 
        // store the its subtree 
        if (root.left != null)  
        { 
            result.add(root.left); 
        } 
        if (root.right != null) 
        { 
            result.add(root.right); 
        } 
        return null; 
    } 
    return root; 
} 
// perform inorder traversal 
static void printinordertree(node root) 
{ 
    if (root == null) 
        return; 
    printinordertree(root.left); 
    console.write(root.key   " "); 
    printinordertree(root.right); 
} 
// function to print the forests 
static void printforests(node root,  
                         int []arr, int n) 
{ 
    for(int i = 0; i < n; i  ) 
    { 
        mp.add(arr[i], true); 
    } 
    // stores the remaining nodes 
    list result = new list(); 
    if (treepruning(root, result) != null) 
        result.add(root); 
    // print the inorder traversal of forests 
    for(int i = 0; i < result.count; i  )  
    { 
        printinordertree(result[i]); 
        console.writeline(); 
    } 
} 
// driver code 
public static void main(string[] args) 
{ 
    node root = newnode(1); 
    root.left = newnode(12); 
    root.right = newnode(13); 
    root.right.left = newnode(14); 
    root.right.right = newnode(15); 
    root.right.left.left = newnode(21); 
    root.right.left.right = newnode(22); 
    root.right.right.left = newnode(23); 
    root.right.right.right = newnode(24); 
    int []arr = { 14, 23, 1 }; 
    int n = arr.length; 
    printforests(root, arr, n); 
} 
} 
// this code is contributed by amit katiyar 

输出： 

21 
22 
12 
13 15 24

时间复杂度：o(n)。

辅助空间：o(1)。

麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处

本文链接：http://www.moonapi.com/news/38713.html