Tìm khoảng cách từ gốc đến nút cho trước trong cây nhị phân trong C++

Cho cây nhị phân, tìm khoảng cách từ gốc đến nút u. Ví dụ cây như hình, khoảng cách (gốc, 6) = 2, (gốc, 8) = 3.

Sử dụng đệ quy tìm nút ở cây con trái/phải, cập nhật độ dài cho mỗi mức.

Ví dụ

#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; } int getDistance(Node *root, int x) {    if (root == NULL)       return -1;    int dist = -1;    if ((root->data == x) || (dist = getDistance(root->left, x)) >= 0 || (dist = getDistance(root->right, x)) >= 0)       return dist + 1;    return dist; } int main() {    Node* root = getNode(1);    root->left = getNode(2);    root->right = getNode(3);    root->left->left = getNode(4);    root->left->right = getNode(5);    root->right->left = getNode(6);    root->right->right = getNode(7);    root->right->left->right = getNode(8);    cout <<"Distance from root to node 6 is: " << getDistance(root,6);    cout << "\nDistance from root to node 8 is: " << getDistance(root,8); }

Kết quả

Distance from root to node 6 is: 2 Distance from root to node 8 is: 3