Đường viền của cây nhị phân trong C++

Giới thiệu

Cho cây nhị phân. Trả về các giá trị nút trên đường viền (boundary) theo chiều kim đồng hồ ngược, bắt đầu từ gốc. Đường viền bao gồm: gốc, đường viền trái (từ gốc đến nút lá trái nhất), các lá (từ trái sang phải), đường viền phải (từ lá phải nhất lên gốc) – không trùng lặp nút.

Thuật toán: 3 phần riêng biệt

1. Gốc: thêm gốc.
2. Viền trái: từ gốc->left, đi xuống: ưu tiên trái, nếu không có thì phải. Không thêm lá.
3. Các lá: DFS in-order (trái-gốc-phải) thêm tất cả lá.
4. Viền phải: từ gốc->right, đi xuống: ưu tiên phải, nếu không có thì trái. Thêm vào kết quả theo thứ tự ngược (dùng stack hoặc đệ quy hậu tự). Không thêm lá.

Cài đặt C++

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

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    vector boundary;
    void leftBoundary(TreeNode* node) {
        if (!node || (!node->left && !node->right)) return;
        boundary.push_back(node->val);
        if (node->left) leftBoundary(node->left);
        else leftBoundary(node->right);
    }
    void rightBoundary(TreeNode* node) {
        if (!node || (!node->left && !node->right)) return;
        if (node->right) rightBoundary(node->right);
        else rightBoundary(node->left);
        boundary.push_back(node->val); // push sau để ngược thứ tự
    }
    void leaves(TreeNode* node) {
        if (!node) return;
        if (!node->left && !node->right) boundary.push_back(node->val);
        leaves(node->left);
        leaves(node->right);
    }
public:
    vector boundaryOfBinaryTree(TreeNode* root) {
        if (!root) return {};
        boundary.clear();
        boundary.push_back(root->val);
        leftBoundary(root->left);
        leaves(root->left);
        leaves(root->right);
        rightBoundary(root->right);
        return boundary;
    }
};

int main() {
    // Cây ví dụ
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(8);
    root->left->right->left = new TreeNode(9);
    root->left->right->right = new TreeNode(10);
    Solution ob;
    auto ans = ob.boundaryOfBinaryTree(root);
    for (int x : ans) cout << x << ' '; // 1 2 4 7 8 9 10 6 3
    return 0;
}

Phân tích

• Thời gian: O(N) – mỗi nút thăm hằng số lần.
• Không gian: O(H) – stack đệ quy, H = chiều cao.

LeetCode 545 "Boundary of Binary Tree".