LeetCode/235.cpp at master · nitin-maharana/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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/*
 * Written by Nitin Kumar Maharana
 * nitin.maharana@gmail.com
 */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

//Iterative Solution.
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int mn, mx;

        mn = min(p->val, q->val);
        mx = max(p->val, q->val);

        while(root)
        {
            if(root->val < mn)
                root = root->right;
            else if(root->val > mx)
                root = root->left;
            else
                return root;
        }
    }
};

//Recursive Solution.
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p || root == q)
            return root;

        if(root->val < p->val && root->val < q->val)
            return lowestCommonAncestor(root->right, p, q);

        if(root->val > p->val && root->val > q->val)
            return lowestCommonAncestor(root->left, p, q);

        return root;
    }
};

//Recursive Solution. It doesn't assume anything. If any node is not present, returns NULL.
//As well as no need to be distinct nodes.
class Solution {
    TreeNode* lcaUtil(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if(root == nullptr || root == p || root == q)
            return root;

        if(root->val < p->val && root->val < q->val)
            return lcaUtil(root->right, p, q);

        if(root->val > p->val && root->val > q->val)
            return lcaUtil(root->left, p, q);

        return root;
    }

    TreeNode* findNode(TreeNode* root, TreeNode* n)
    {
        if(root == nullptr || root == n)
            return root;

        if(root->val < n->val)
            return findNode(root->right, n);
        else
            return findNode(root->left, n);
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q)
            return root;

        TreeNode *lca = lcaUtil(root, p, q);

        if(findNode(lca, p) && findNode(lca, q))
            return lca;

        return NULL;
    }
};

//Iterative Solution for the above one.
class Solution {
    TreeNode* findNode(TreeNode* root, TreeNode* n)
    {
        while(root)
        {
            if(root == n)
                return root;

            if(root->val < n->val)
                root = root->right;
            else
                root = root->left;
        }

        return NULL;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q)
            return root;

        TreeNode *lca = NULL;
        TreeNode *ptr = root;

        int mn = min(p->val, q->val);
        int mx = max(p->val, q->val);

        while(ptr)
        {
            if(ptr->val < mn)
                ptr = ptr->right;
            else if(ptr->val > mx)
                ptr = ptr->left;
            else
            {
                lca = ptr;
                break;
            }
        }

        if(findNode(lca, p) && findNode(lca, q))
            return lca;

        return NULL;
    }
};