In this Leetcode Lowest Common Ancestor of a Binary Search Tree problem solution we have given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Problem solution in Python.
class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if not root: return elif (root.val >= p.val and root.val <= q.val) or (root.val <= p.val and root.val >= q.val): return root elif root.val > p.val and root.val > q.val: return self.lowestCommonAncestor(root.left,p,q) else: return self.lowestCommonAncestor(root.right,p,q)
Problem solution in Java.
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null) return root; if(root.val==p.val || root.val==q.val) return root; if(root.val>p.val && root.val>q.val) return lowestCommonAncestor(root.left,p,q); if(root.val<p.val && root.val<q.val) return lowestCommonAncestor(root.right,p,q); return root; } }
Problem solution in C++.
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { TreeNode* ll = p; TreeNode* hh = q; if(p->val > q->val) { ll=q; hh=p; } while((ll->val!=root->val && hh->val!=root->val) && (ll->val > root->val || root->val > hh->val)) { if(ll->val > root->val) { root=root->right; } else if(root->val > hh->val) { root=root->left; } } return root; } };
Problem solution in C.
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) { struct TreeNode *result = root; int v1 = p->val, v2 = q->val; p = q = root; while (p && q) { if (p == q) result = p; else break; if (p->val > v1) p = p->left; else if (p->val < v1) p = p->right; else break; if (q->val > v2) q = q->left; else if (q->val < v2) q = q->right; else break; } return result; }
0 Comments