การตัดแต่งต้นไม้แบนารี (Binary Tree Pruning) ใน C++

การตัดแต่งต้นไม้แบนารี (Binary Tree Pruning)

ให้รากของต้นไม้แบนารีที่ค่าโหนดเป็น 0 หรือ 1 ต้องการตัดแต่งต้นไม้ย่อยที่ไม่มีค่า 1 ออกทั้งหมด (คือถ้าต้นไม้ย่อยไม่มี 1 เลย ให้ลบทิ้ง)

ตัวอย่าง: ต้นไม้ [1,1,0,1,1,0,1,0] หลังตัดแต่งจะเหลือ [1,1,0,1,1,1]

ขั้นตอนการแก้ปัญหา (DFS Post-order)

1. กำหนดฟังก์ชัน pruneTree(node):
2. ถ้า node == null คืนค่า null
3. node.left = pruneTree(node.left)
4. node.right = pruneTree(node.right)
5. ถ้า node.left == null && node.right == null && node.val == 0 คืนค่า null (ลบโหนดนี้)
6. มิฉะนั้นคืนค่า node

ตัวอย่างโค้ด 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;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [1,1,0,1,1,0,1,0]

Output: [1, 1, 0, 1, 1, 1]