leetcode-practice/cpp/236.lowest-common-ancestor-of-a-binary-tree.cpp at master · Heatwave/leetcode-practice · 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
#include <iostream>
#include <vector>

using namespace std;

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

class Solution
{
  private:
    int pVal, qVal;
    vector<struct TreeNode *> v;
    vector<struct TreeNode *> pAncestor;
    vector<struct TreeNode *> qAncestor;

    void preorderTraversal(TreeNode *node)
    {
        v.push_back(node);
        if (node->val == pVal)
        {
            pAncestor = v;
        }
        if (node->val == qVal)
        {
            qAncestor = v;
        }

        if (node->left != NULL)
            preorderTraversal(node->left);
        if (node->right != NULL)
            preorderTraversal(node->right);

        v.pop_back();
    }

  public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        pVal = p->val;
        qVal = q->val;
        preorderTraversal(root);

        TreeNode *result = NULL;

        int i = pAncestor.size() - 1, j = qAncestor.size() - 1;

        for (; i >= 0; i--)
        {
            for (int k = j; k >= 0; k--)
            {
                if (qAncestor[k]->val == pAncestor[i]->val)
                {
                    result = qAncestor[k];
                    break;
                }
            }
            if (result != NULL)
                break;
        }

        return result;
    }
};

int main(int argc, char const *argv[])
{
    struct TreeNode *tree = new TreeNode(1);
    struct TreeNode *treeLeft = new TreeNode(2);
    struct TreeNode *treeRight = new TreeNode(3);
    struct TreeNode *treeLeftLeft = new TreeNode(4);
    struct TreeNode *treeLeftRight = new TreeNode(5);
    struct TreeNode *treeRightLeft = new TreeNode(6);
    struct TreeNode *treeRightRight = new TreeNode(7);
    struct TreeNode *treeLeftRightLeft = new TreeNode(8);
    struct TreeNode *treeLeftRightRight = new TreeNode(9);

    tree->left = treeLeft;
    tree->right = treeRight;
    treeLeft->left = treeLeftLeft;
    treeLeft->right = treeLeftRight;
    treeRight->left = treeRightLeft;
    treeRight->right = treeRightRight;
    treeLeftRight->left = treeLeftRightLeft;
    treeLeftRight->right = treeLeftRightRight;

    Solution solution;
    struct TreeNode *ancestor = solution.lowestCommonAncestor(tree, treeLeftRight, treeLeftRightRight);
    cout << "ancestor: " << ancestor->val << endl;

    return 0;
}