Cắt tỉa cây nhị phân trong C++

Cho nút gốc của cây nhị phân, mỗi nút giá trị 0 hoặc 1. Trả về cây sau khi xóa mọi cây con không chứa giá trị 1. Ví dụ cây đầu vào cho kết quả cây đã cắt tỉa.

Giải thuật

• Định nghĩa hàm đệ quy solve(node):
  • Nếu node == null trả về null.
  • node->left = solve(node->left)
  • node->right = solve(node->right)
  • Nếu node->left == null && node->right == null && node->val == 0 trả về null.
  • Trả về node.

Ví dụ mã C++

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

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

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;
    }
};

Đầu vào

[1,1,0,1,1,0,1,0]

Đầu ra

[1, 1, 0, 1, 1, 1, ]