Tổng các nút ảnh đối xứng trong cây nhị phân hoàn chỉnh theo inorder trong C++

Cho cây nhị phân hoàn chỉnh (complete binary tree), tính tổng các cặp nút ảnh đối xứng (mirror) khi duyệt inorder cây con trái.

Duyệt inorder cây con trái, mỗi nút cộng với nút ảnh đối xứng ở cây con phải.

Ví dụ

Đầu ra: 9 9 17 2

Giải thích: Inorder trái: 5-7-8-1. Cộng với ảnh đối xứng:

5 + 4 = 9
7 + 2 = 9
8 + 9 = 17
1 + 1 = 2

Thuật toán

Dùng 2 con trỏ: root duyệt cây trái, rootMirror duyệt cây phải (đối xứng).

void inorderMirror(Node* root, Node* rootMirror) {
    if (!root->left && !rootMirror->right) return;
    inorderMirror(root->left, rootMirror->right);
    cout << (root->left->data + rootMirror->right->data) << endl;
    inorderMirror(root->right, rootMirror->left);
}

Ví dụ mã nguồn

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int d) { data = d; left = right = NULL; }
};

void inorderMirror(Node* root, Node* rootMirror) {
    if (!root->left && !rootMirror->right) return;
    inorderMirror(root->left, rootMirror->right);
    cout << (root->left->data + rootMirror->right->data) << endl;
    inorderMirror(root->right, rootMirror->left);
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(7);
    root->right = new Node(2);
    root->left->left = new Node(5);
    root->left->right = new Node(8);
    root->right->left = new Node(9);
    root->right->right = new Node(4);
    
    cout << "Tổng nút và ảnh đối xứng:\n";
    inorderMirror(root, root);
    if (root) cout << (root->data + root->data);
    return 0;
}

Kết quả

Tổng nút và ảnh đối xứng:
9
9
17
2