Add One Row to Tree – เพิ่มแถวโหนดใน Binary Tree C++

ปัญหา: Add One Row to Tree

กำหนด Binary Tree, ค่า v, และความลึก d เพิ่มแถวโหนดใหม่ค่า v ที่ความลึก d (ราก = ความลึก 1)

กฎการเพิ่ม

• d = 1: สร้างรากใหม่ค่า v, ต้นไม้เดิมเป็นลูกซ้าย
• d > 1: สำหรับโหนดทุกตัวที่ความลึก d-1
  • สร้างโหนดใหม่ 2 ตัวค่า v เป็นลูกซ้ายและลูกขวา
  • ลูกซ้ายเดิม → เป็นลูกซ้ายของโหนดใหม่ซ้าย
  • ลูกขวาเดิม → เป็นลูกขวาของโหนดใหม่ขวา

ตัวอย่าง

Tree: [4,2,6,3,1,5], v = 1, d = 2

ก่อน:       4              หลัง:        4
           / \                    / \
          2   6                  1   1
         / \ / \                /     \
        3  1 5                 2       6
                                / \     / \
                               3  1    5

แนวทางแก้ปัญหา: DFS หรือ BFS

วิธีที่ 1: DFS Recursive (Simple)

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if (d == 1) {
            TreeNode* newRoot = new TreeNode(v);
            newRoot->left = root;
            return newRoot;
        }
        dfs(root, v, d, 1);
        return root;
    }

    void dfs(TreeNode* node, int v, int d, int depth) {
        if (!node) return;
        if (depth == d - 1) {
            TreeNode* left = new TreeNode(v);
            TreeNode* right = new TreeNode(v);
            left->left = node->left;
            right->right = node->right;
            node->left = left;
            node->right = right;
            return;
        }
        dfs(node->left, v, d, depth + 1);
        dfs(node->right, v, d, depth + 1);
    }
};

วิธีที่ 2: BFS Iterative (ต้นฉบับ)

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if (d == 1) {
            TreeNode* temp = new TreeNode(v);
            temp->left = root;
            return temp;
        }

        queue<pair<TreeNode*, int>> q;
        q.emplace(root, 1);

        while (!q.empty()) {
            auto [node, depth] = q.front(); q.pop();
            if (depth == d - 1) {
                TreeNode* left = new TreeNode(v);
                TreeNode* right = new TreeNode(v);
                left->left = node->left;
                right->right = node->right;
                node->left = left;
                node->right = right;
            } else {
                if (node->left) q.emplace(node->left, depth + 1);
                if (node->right) q.emplace(node->right, depth + 1);
            }
        }
        return root;
    }
};

โครงสร้าง TreeNode และ Helper

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// สร้าง tree จาก level-order (0 = null)
TreeNode* buildTree(vector<int> v) {
    if (v.empty() || v[0] == 0) return nullptr;
    TreeNode* root = new TreeNode(v[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < v.size()) {
        TreeNode* cur = q.front(); q.pop();
        if (i < v.size() && v[i] != 0) {
            cur->left = new TreeNode(v[i]);
            q.push(cur->left);
        }
        i++;
        if (i < v.size() && v[i] != 0) {
            cur->right = new TreeNode(v[i]);
            q.push(cur->right);
        }
        i++;
    }
    return root;
}

// พิมพ์ level-order
void printTree(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        if (cur) {
            cout << cur->val << ' ';
            q.push(cur->left);
            q.push(cur->right);
        } else {
            cout << "null ";
        }
    }
    cout << '\n';
}

ความซับซ้อน

• เวลา: O(N) – เยี่ยมทุกโหนดสูงสุด 1 ครั้ง
• พื้นที่: O(H) stack (DFS) หรือ O(W) queue (BFS) – H = ความสูง, W = ความกว้าง

ข้อสังเกต

• LeetCode 623
• DFS เรียบง่ายกว่า BFS สำหรับปัญหานี้
• จัดการกรณี d = 1 แยกต่างหาก
• โหนดที่ depth = d-1 อาจมีลูกซ้าย/ขวาเป็น null → โหนดใหม่จะมีลูกเป็น null ตามไป