Chương trình cắt tỉa cây nhị phân trong C++

Giả sử có một cây nhị phân, giá trị mỗi nút là 0 hoặc 1. Ta phải tìm lại cây đó nơi mọi cây con không chứa 1 đã bị xóa.

Để giải quyết, ta làm theo các bước sau:

• Định nghĩa phương pháp đệ quy solve(), nhận nút. Phương pháp như sau:
• Nếu nút null, trả về null
• left của nút := solve(left của nút)
• right của nút := solve(right của nút)
• nếu left và right đều null và giá trị nút là 0, trả về null
• trả về nút

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = NULL;
        right = NULL;
    }
};

void inorder(TreeNode *root) {
    if(root) {
        inorder(root->left);
        cout << root->val << ", ";
        inorder(root->right);
    }
}

class Solution {
public:
    TreeNode* pruneTree(TreeNode* node) {
        if(!node) return NULL;
        node->left = pruneTree(node->left);
        node->right = pruneTree(node->right);
        if(!node->left && !node->right && !node->val) {
            return NULL;
        }
        return node;
    }
};

int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(1);
    root->right = new TreeNode(0);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(1);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(1);
    root->left->left->left = new TreeNode(0);
    Solution ob;
    inorder(ob.pruneTree(root));
    return 0;
}

Đầu vào

TreeNode *root = new TreeNode(1); root->left = new TreeNode(1); root->right = new TreeNode(0); root->left->left = new TreeNode(1); root->left->right = new TreeNode(1); root->right->left = new TreeNode(0); root->right->right = new TreeNode(1); root->left->left->left = new TreeNode(0);

Đầu ra

1, 1, 1, 1, 0, 1,