Boundary of Binary Tree – หาขอบของต้นไม้ใน C++

ปัญหา: Boundary of Binary Tree

กำหนด Binary Tree หา ขอบ (boundary) ในทิศทาง วนทวนเข็มนาฬิกา เริ่มจากราก
ประกอบด้วย 3 ส่วน (ไม่ซ้ำโหนด):

1. Left Boundary: ราก → โหนดซ้ายสุด (ไม่รวมใบ)
2. Leaves: ใบทั้งหมด (ซ้ายไปขวา)
3. Right Boundary: โหนดขวาสุด → ราก (ไม่รวมใบ, เรียกทวนลำดับ)

ตัวอย่าง

      1
     / \
    2   3
   / \ / \
  4  5 6  7
 / \   / \
8   9 10

Boundary: [1, 2, 4, 8, 9, 10, 6, 7, 3]

แนวทางแก้ปัญหา: 3 DFS แยกส่วน

Left Boundary

จาก root->left ลงไป: เพิ่มโหนด → ถ้ามีซ้าย ไปซ้าย ไม่งั้นไปขวา → หยุดที่ใบ

Right Boundary

จาก root->right ลงไป: ถ้ามีขวา ไปขวา ไม่งั้นไปซ้าย → หยุดที่ใบ → เพิ่มโหนดตอน backtrack (เพื่อให้เรียงจากใต้ขึ้นมา)

Leaves

Inorder traversal: เพิ่มโหนดที่ไม่มีลูก

ตัวอย่างโค้ด C++

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

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

class Solution {
    vector<int> boundary;

    void leftBoundary(TreeNode* node) {
        if (!node || (!node->left && !node->right)) return;
        boundary.push_back(node->val);
        if (node->left) leftBoundary(node->left);
        else leftBoundary(node->right);
    }

    void rightBoundary(TreeNode* node) {
        if (!node || (!node->left && !node->right)) return;
        if (node->right) rightBoundary(node->right);
        else rightBoundary(node->left);
        boundary.push_back(node->val); // post-order: add after children
    }

    void leaves(TreeNode* node) {
        if (!node) return;
        if (!node->left && !node->right) {
            boundary.push_back(node->val);
            return;
        }
        leaves(node->left);
        leaves(node->right);
    }

public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        boundary.clear();
        if (!root) return boundary;

        boundary.push_back(root->val);
        leftBoundary(root->left);
        leaves(root->left);
        leaves(root->right);
        rightBoundary(root->right);
        return boundary;
    }
};

int main() {
    Solution ob;
    // Build tree from example
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    root->left->left->left = new TreeNode(8);
    root->left->left->right = new TreeNode(9);
    root->right->left->left = new TreeNode(10);

    auto ans = ob.boundaryOfBinaryTree(root);
    for (int x : ans) cout << x << ' '; // 1 2 4 8 9 10 6 7 3
    return 0;
}

ความซับซ้อน

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

ข้อสังเกต

• LeetCode 545
• สำคัญ: Right boundary ต้องเพิ่มค่า หลัง recursion (post-order) เพื่อให้เรียงจากใต้ขึ้น
• Left boundary และ Right boundary ไม่รวมใบ – ใบจัดการใน leaves()
• กรณี root ไม่มี left/right subtree → root เองเป็น boundary นั้น