Tìm lá gần nhất trong cây nhị phân C++

Cho cây nhị phân có lá ở các cấp khác nhau. Con trỏ trỏ đến một nút. Tìm khoảng cách đến lá gần nhất từ nút được trỏ. Cây như sau:

Lá là 2, -2, 6. Nếu con trỏ trỏ -5, lá gần nhất từ -5 ở khoảng cách 1.

Giải quyết: duyệt cây con gốc tại nút cho trước, tìm lá gần nhất trong cây con, lưu khoảng cách. Duyệt từ gốc, nếu nút x ở cây con trái thì tìm cây con phải và ngược lại.

Ví dụ mã nguồn

#include<iostream> using namespace std; class Node {    public:       int data;    Node *left, *right; }; Node* getNode(int data) {    Node* node = new Node;    node->data = data;    node->left = node->right = NULL;    return node; } void getLeafDownward(Node *root, int level, int *minDist) {    if (root == NULL)       return ;    if (root->left == NULL && root->right == NULL) {       if (level < (*minDist))          *minDist = level;       return;    }    getLeafDownward(root->left, level+1, minDist);    getLeafDownward(root->right, level+1, minDist); } int getFromParent(Node * root, Node *x, int *minDist) {    if (root == NULL)       return -1;    if (root == x)       return 0;    int l = getFromParent(root->left, x, minDist);    if (l != -1) {       getLeafDownward(root->right, l+2, minDist);       return l+1;    }    int r = getFromParent(root->right, x, minDist);    if (r != -1) {       getLeafDownward(root->left, r+2, minDist);       return r+1;    }    return -1; } int minimumDistance(Node *root, Node *x) {    int minDist = INT8_MAX;    getLeafDownward(x, 0, &minDist);    getFromParent(root, x, &minDist);    return minDist; } int main() {    Node* root = getNode(4);    root->left = getNode(2);    root->right = getNode(-5);    root->right->left = getNode(-2);    root->right->right = getNode(6);    Node *x = root->right;    cout << "Closest distance of leaf from " << x->data <<" is: " << minimumDistance(root, x); }

Kết quả

Closest distance of leaf from -5 is: 1