Lật ngược cây nhị phân (Binary Tree Upside Down) trong C++

Cho cây nhị phân mà mọi nút phải là lá hoặc có anh em trái. Lật ngược cây sao cho nút phải ban đầu thành lá trái của cây mới. Trả về gốc mới.

Ví dụ

Đầu vào: [1,2,3,4,5]

Đầu ra: [4,5,2,null,null,3,1]

Thuật toán đệ quy

Hàm solve(node, parent, sibling) trả về gốc mới của cây con sau khi lật:

1. Nếu node null → trả về NULL.
2. Lưu child = node->left, currSib = node->right.
3. Gán node->left = sibling, node->right = parent (lật hướng).
4. Nếu child và currSib đều null → node là lá mới, trả về node.
5. Gọi đệ quy: return solve(child, node, currSib).

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) : val(data), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* solve(TreeNode* node, TreeNode* parent, TreeNode* sibling) {
        if (!node) return NULL;
        TreeNode* child = node->left;
        TreeNode* currSib = node->right;
        node->left = sibling;
        node->right = parent;
        if (!child && !currSib) return node;
        return solve(child, node, currSib);
    }
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        return solve(root, NULL, NULL);
    }
};

Độ phức tạp

• Thời gian: O(N) - duyệt mỗi nút một lần.
• Không gian: O(H) - ngăn xếp đệ quy, H là chiều cao cây.

Kết quả kiểm thử

Đầu vào: [1,2,3,4,5]
Đầu ra: [4,5,2,null,null,3,1]