minimum_path_in_binary_tree/bt.h at main · florell/minimum_path_in_binary_tree · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int data): data(data), left(nullptr), right(nullptr) {}
};

pair<pair<vector<int>, int>, pair<vector<int>, int>> get_max_path(Node* root)
{
    if (!root)
    {
        return {{{}, 0},{{}, 0}};
    }

    pair<pair<vector<int>, int>, pair<vector<int>, int>> left(get_max_path(root->left)), right(get_max_path(root->right)), ans;

    if (left.second.second > right.second.second || (left.second.second == right.second.second && left.second.first.size() <= right.second.first.size()))
    {
        if (left.second.second < 0)
        {
            ans.second = {{root->data}, root->data};
        }
        else
        {
            ans.second = left.second;
            ans.second.first.emplace_back(root->data);
            ans.second.second += root->data;
        }
    }
    else
    {
        if (right.second.second < 0)
        {
            ans.second = {{root->data}, root->data};
        }
        else
        {
            ans.second = right.second;
            ans.second.first.emplace_back(root->data);
            ans.second.second += root->data;
        }
    }
    if (ans.second.second <= 0)
    {
        ans.second = {{}, 0};
    }

    for (int & i : left.second.first)
    {
        ans.first.first.emplace_back(i);
        ans.first.second += i;
    }

    ans.first.first.emplace_back(root->data);
    ans.first.second += root->data;

    for (int & i : right.second.first)
    {
        ans.first.first.emplace_back(i);
        ans.first.second += i;
    }

    if (left.first.second > 0 && (ans.first.second < left.first.second || (ans.first.second == left.first.second && ans.first.first.size() < left.first.first.size())))
    {
        ans.first = left.first;
    }

    if (right.first.second > 0 && (ans.first.second < right.first.second || (ans.first.second == right.first.second && ans.first.first.size() < right.first.first.size())))
    {
        ans.first = right.first;
    }

    if (ans.first.second < root->data)
    {
        ans.first = {{root->data}, root->data};
    }

    return ans;
}

class BinaryTree {
public:
    Node *root;

    BinaryTree() {
        root = nullptr;
    }

    void insert(int data) {
        Node *node = new Node(data);
        if (root == nullptr) {
            root = node;
        } else {
            Node *current = root;
            Node *parent;
            while (true) {
                parent = current;
                if (data < current->data) {
                    current = current->left;
                    if (current == nullptr) {
                        parent->left = node;
                        break;
                    }
                } else {
                    current = current->right;
                    if (current == nullptr) {
                        parent->right = node;
                        break;
                    }
                }
            }
        }
    }

    void printTree(Node *node, bool isRight = false, const std::string& indent = "", bool isFirst = true) {
        if (node == nullptr) {
            return;
        }

        printTree(node->right, true, indent + (isRight ? "     " : "│    "), false);

        std::cout << (isFirst ? "" : indent);
        if (isRight) {
            std::cout << "┌───";
        } else {
            std::cout << "└───";
        }
        std::cout << node->data << std::endl;

        printTree(node->left, false, indent + (isRight ? "│    " : "     "), false);
    }
};