leetcode/1123.cpp at main · h3902340/leetcode · 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
#include <utility>
#include <_printf.h>
#include <stack>
#include <queue>
using namespace std;

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

class Solution
{
public:
    TreeNode *lcaDeepestLeaves(TreeNode *root)
    {
        pair<int, TreeNode *> ans = lcaDeepestLeavesRecursive(root);
        return ans.second;
    }

private:
    pair<int, TreeNode *> lcaDeepestLeavesRecursive(TreeNode *root)
    {
        if (!root)
        {
            return {0, nullptr};
        }
        pair<int, TreeNode *> d1 = lcaDeepestLeavesRecursive(root->left);
        pair<int, TreeNode *> d2 = lcaDeepestLeavesRecursive(root->right);
        if (d1.first == d2.first)
        {
            return {d1.first + 1, root};
        }
        else if (d1 > d2)
        {
            return {d1.first + 1, d1.second};
        }
        else
        {
            return {d2.first + 1, d2.second};
        }
    }
};

const int arrLen = 9;
int nodes[arrLen]{1, 2, -1, 3, 4, -1, 6, -1, 5};

int main()
{
    TreeNode *treeNodes[arrLen];
    int curr = 1;
    int next = 1;
    treeNodes[0] = new TreeNode(nodes[0]);
    for (int i = 0; i < arrLen; i++)
    {
        if (i == curr)
        {
            curr = next;
        }
        TreeNode *node = treeNodes[i];
        if (!node)
        {
            continue;
        }
        if (next >= arrLen || nodes[next] == -1)
        {
            node->left = nullptr;
        }
        else
        {
            node->left = new TreeNode(nodes[next]);
        }
        if (next < arrLen)
        {
            treeNodes[next] = node->left;
        }
        next++;
        if (next >= arrLen || nodes[next] == -1)
        {
            node->right = nullptr;
        }
        else
        {
            node->right = new TreeNode(nodes[next]);
        }
        if (next < arrLen)
        {
            treeNodes[next] = node->right;
        }
        next++;
    }
    Solution sol;
    TreeNode *lca = sol.lcaDeepestLeaves(treeNodes[0]);
    printf("lca = [%d", lca->val);
    queue<TreeNode *> queue;
    queue.push(lca->left);
    queue.push(lca->right);
    int i = (lca->left != nullptr) + (lca->right != nullptr);
    while (!queue.empty() && i > 0)
    {
        TreeNode *f = queue.front();
        queue.pop();
        if (f)
        {
            i--;
            printf(",%d", f->val);
            queue.push(f->left);
            queue.push(f->right);
            i += (f->left != nullptr);
            i += (f->right != nullptr);
        }
        else
        {
            printf(",null");
        }
    }
    printf("]\n");
    return 0;
}