พิมพ์ Leaf Nodes ของ Binary Tree ขวา-ซ้าย ใน C++

ภาพรวมปัญหา

ได้รับ Binary Tree ต้องพิมพ์ Leaf Nodes จากขวาไปซ้าย

ตัวอย่าง

Output: 7 4 1

วิธีแก้ปัญหา 2 แบบ

1. Preorder Traversal (Recursive)

เยี่ยม Root → ขวา → ซ้าย ถ้าเป็น Leaf พิมพ์ทันที

2. Postorder Traversal (Iterative with Stack)

ใช้ Stack ทำ Postorder (ขวา-ซ้าย-ราก) พิมพ์ตอนเจอ Leaf

ตัวอย่างโค้ด C++ (ทั้ง 2 วิธี)

// วิธี 1: Preorder Recursive
void findLeafNode(Node* root) {
    if (!root) return;
    if (!root->left && !root->right) {
        cout << root->data << "\t";
        return;
    }
    if (root->right) findLeafNode(root->right);
    if (root->left) findLeafNode(root->left);
}

// วิธี 2: Postorder Iterative
void findLeafNode(Node* tree) {
    stack<Node*> treeStack;
    while (1) {
        if (tree) {
            treeStack.push(tree);
            tree = tree->right;
        } else {
            if (treeStack.empty()) break;
            else {
                if (treeStack.top()->left == NULL) {
                    tree = treeStack.top();
                    treeStack.pop();
                    if (tree->right == NULL)
                        cout << tree->data << "\t";
                }
                while (tree == treeStack.top()->left) {
                    tree = treeStack.top();
                    treeStack.pop();
                    if (treeStack.empty()) break;
                }
                if (!treeStack.empty())
                    tree = treeStack.top()->left;
                else
                    tree = NULL;
            }
        }
    }
}

ผลลัพธ์ (Output)

Leaf nodes of the tree from right to left are:
18 2 98 8