โปรแกรม C++ หา Deepest Left Leaf ใน Binary Tree

Binary Tree เป็นต้นไม้ที่มีลูกสูงสุด 2 ตัว ระบุเป็น left child และ right child นี่คือโปรแกรม C++ สำหรับหา Deepest Left Leaf (ใบซ้ายลึกที่สุด) ใน Binary Tree

อัลกอริทึม

เริ่มต้น
  ฟังก์ชัน deepestLLeafutil() หา deepest left leaf ใน binary tree:
    lvel คือ level ของโหนดปัจจุบัน
    maxlvel คือ pointer ไปยัง deepest left leaf node ที่พบจนถึงตอนนี้
    isLeft บอกว่าโหนดนี้เป็น left child ของ parent หรือไม่
    resPtr คือ pointer ไปยังผลลัพธ์
    ถ้า root เท่ากับ NULL แล้ว คืนค่า
    อัปเดตผลลัพธ์ถ้าโหนดนี้เป็น left leaf และ level มากกว่า max level ปัจจุบัน
    เรียกฟังก์ชัน deepestLLeafutil() แบบ recursive สำหรับ subtree ซ้ายและขวา
สิ้นสุด

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

#include <iostream>
using namespace std;

struct n {
    int v;
    n *l, *r;
};

void deepestLLeafutil(n *root, int lvel, int *maxvel, bool isLeft, n **resPtr) {
    if (root == NULL) return;
    if (isLeft && !root->l && !root->r && lvel > *maxvel) {
        *resPtr = root;
        *maxvel = lvel;
        return;
    }
    deepestLLeafutil(root->l, lvel + 1, maxvel, true, resPtr);
    deepestLLeafutil(root->r, lvel + 1, maxvel, false, resPtr);
}

n* deepestLLeaf(n *root) {
    int maxlevel = 0;
    n *res = NULL;
    deepestLLeafutil(root, 0, &maxlevel, false, &res);
    return res;
}

n *newnode(int d) {
    n *t = new n;
    t->v = d;
    t->l = t->r = NULL;
    return t;
}

int main() {
    n* root = newnode(9);
    root->l = newnode(7);
    root->r = newnode(10);
    root->l->l = newnode(6);
    root->r->l = newnode(8);
    root->r->r = newnode(19);
    root->r->l->r = newnode(4);
    root->r->r->r = newnode(20);
    n *res = deepestLLeaf(root);
    if (res)
        cout << "The deepest left leaf is " << res->v;
    else
        cout << "There is no left leaf in the given tree";
    return 0;
}

ผลลัพธ์

The deepest left leaf is 6