# 如何find任意二叉树中两个节点的最低共同祖先？

``struct node { int data; struct node *left; struct node *right; };` `

### 30 Solutions collect form web for “如何find任意二叉树中两个节点的最低共同祖先？”

Nick Johnson是正确的，如果没有父指针，那么O（n）时间复杂度algorithm是最好的。）对于该algorithm的简单recursion版本，请参阅Kinding的post中的代码，该代码在O（n）时间。

`root`开始向下移动，如果发现有`p``q`作为其直接子节点的任何节点，那么它是LCA。 （编辑 – 这应该是如果`p``q`是节点的值，则返回它，否则当`p``q`中的一个是另一个的直接子节点时，它将失败。

` `treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) { // no root no LCA. if(!root) { return NULL; } // if either p or q is the root then root is LCA. if(root==p || root==q) { return root; } else { // get LCA of p and q in left subtree. treeNodePtr l=findLCA(root->left , p , q); // get LCA of p and q in right subtree. treeNodePtr r=findLCA(root->right , p, q); // if one of p or q is in leftsubtree and other is in right // then root it the LCA. if(l && r) { return root; } // else if l is not null, l is LCA. else if(l) { return l; } else { return r; } } }` `

` `treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) { // no root no LCA. if(!root) { return NULL; } // if either p or q is direct child of root then root is LCA. if(root->left==p || root->left==q || root->right ==p || root->right ==q) { return root; } else { // get LCA of p and q in left subtree. treeNodePtr l=findLCA(root->left , p , q); // get LCA of p and q in right subtree. treeNodePtr r=findLCA(root->right , p, q); // if one of p or q is in leftsubtree and other is in right // then root it the LCA. if(l && r) { return root; } // else if l is not null, l is LCA. else if(l) { return l; } else { return r; } } }` `

` `public static Node LCA(Node root, Node a, Node b) { if (root == null) { return null; } // If the root is one of a or b, then it is the LCA if (root == a || root == b) { return root; } Node left = LCA(root.left, a, b); Node right = LCA(root.right, a, b); // If both nodes lie in left or right then their LCA is in left or right, // Otherwise root is their LCA if (left != null && right != null) { return root; } return (left != null) ? left : right; }` `

` `findLowestCommonAncestor(v,w): depth_vv = depth(v); depth_ww = depth(w); vv = v; ww = w; while( depth_vv != depth_ww ) { if ( depth_vv > depth_ww ) { vv = parent(vv); depth_vv--; else { ww = parent(ww); depth_ww--; } } while( vv != ww ) { vv = parent(vv); ww = parent(ww); } return vv;` `

` `depth(v): int d = 0; vv = v; while ( vv is not root ) { vv = parent(vv); d++; } return d;` `

` ` tree_node_type *LowestCommonAncestor( tree_node_type *root , tree_node_type *p , tree_node_type *q) { tree_node_type *l , *r , *temp; if(root==NULL) { return NULL; } if(root->left==p || root->left==q || root->right ==p || root->right ==q) { return root; } else { l=LowestCommonAncestor(root->left , p , q); r=LowestCommonAncestor(root->right , p, q); if(l!=NULL && r!=NULL) { return root; } else { temp = (l!=NULL)?l:r; return temp; } } }` `

Tarjan的离线最小公共祖先algorithm已经足够了（参见Wikipedia ）。 维基百科上有更多的问题（最常见的祖先问题）。

• 使用二进制search在树中查找给定节点Node1，并将所有在此进程中访问的节点保存在一个数组中，如A1所示。 时间 – O（logn），空间 – O（logn）
• 使用二进制search在树中find给定的节点2，并将在此过程中访问的所有节点保存在数组中，如A2。 时间 – O（logn），空间 – O（logn）
• 如果A1列表或A2列表是空的，那么一个节点不存在，所以没有共同的祖先。
• 如果A1列表和A2列表非空，那么查看列表直到find不匹配的节点。 只要你find这样一个节点，那么之前的节点是共同的祖先。

testing用例。 [1]节点n1和n2都在树中，并驻留在其父节点的任一侧。 [2]节点n1或n2是根，LCA是根。 [3]只有n1或n2在树中，LCA将是树根的左子树的根节点，或者LCA将是树根的右子树的根节点。

[4] n1或n2在树中，没有LCA。 [5] n1和n2都是相邻的直线，LCA将是n1或n2，它们都是靠近树的根的。

` `//find the search node below root bool findNode(node* root, node* search) { //base case if(root == NULL) return false; if(root->val == search->val) return true; //search for the node in the left and right subtrees, if found in either return true return (findNode(root->left, search) || findNode(root->right, search)); } //returns the LCA, n1 & n2 are the 2 nodes for which we are //establishing the LCA for node* getLCA(node* root, node* n1, node* n2) { //base case if(root == NULL) return NULL; //If 1 of the nodes is the root then the root is the LCA //no need to recurse. if(n1 == root || n2 == root) return root; //check on which side of the root n1 and n2 reside bool n1OnLeft = findNode(root->left, n1); bool n2OnLeft = findNode(root->left, n2); //n1 & n2 are on different sides of the root, so root is the LCA if(n1OnLeft != n2OnLeft) return root; //if both n1 & n2 are on the left of the root traverse left sub tree only //to find the node where n1 & n2 diverge otherwise traverse right subtree if(n1OnLeft) return getLCA(root->left, n1, n2); else return getLCA(root->right, n1, n2); }` `

python

` `def lowestCommonAncestor(self, root, p, q): while (root.val - p.val) * (root.val - q.val) > 0: root = (root.left, root.right)[p.val > root.val] return root` `

Java的

` `public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while ((root.val - p.val) * (root.val - q.val) > 0) root = p.val < root.val ? root.left : root.right; return root; }` `

recursion

python

` `def lowestCommonAncestor(self, root, p, q): next = p.val < root.val > q.val and root.left or \ p.val > root.val < q.val and root.right return self.lowestCommonAncestor(next, p, q) if next else root` `

Java的

` `public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { return (root.val - p.val) * (root.val - q.val) < 1 ? root : lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q); }` `

` `abstract class Tree case class Node(a:Int, left:Tree, right:Tree) extends Tree case class Leaf(a:Int) extends Tree def lca(tree:Tree, a:Int, b:Int):Tree = { tree match { case Node(ab,l,r) => { if(ab==a || ab ==b) tree else { val temp = lca(l,a,b); val temp2 = lca(r,a,b); if(temp!=null && temp2 !=null) tree else if (temp==null && temp2==null) null else if (temp==null) r else l } } case Leaf(ab) => if(ab==a || ab ==b) tree else null } }` `
` `Node *LCA(Node *root, Node *p, Node *q) { if (!root) return NULL; if (root == p || root == q) return root; Node *L = LCA(root->left, p, q); Node *R = LCA(root->right, p, q); if (L && R) return root; // if p and q are on both sides return L ? L : R; // either one of p,q is on one side OR p,q is not in L&R subtrees }` `

` `int get_bits(unsigned int x) { int high = 31; int low = 0,mid; while(high>=low) { mid = (high+low)/2; if(1<<mid==x) return mid+1; if(1<<mid<x) { low = mid+1; } else { high = mid-1; } } if(1<<mid>x) return mid; return mid+1; } unsigned int Common_Ancestor(unsigned int x,unsigned int y) { int xbits = get_bits(x); int ybits = get_bits(y); int diff,kbits; unsigned int k; if(xbits>ybits) { diff = xbits-ybits; x = x >> diff; } else if(xbits<ybits) { diff = ybits-xbits; y = y >> diff; } k = x^y; kbits = get_bits(k); return y>>kbits; }` `

1. 获取代表x和y使用二进制search的位是O（log（32））
2. x和y的二进制表示法的通用前缀是共同的祖先
3. 无论哪一个以较大的比特数表示由k >> diff带到相同的比特
4. k = x ^ y erazes x和y的通用前缀
5. find代表剩余后缀的位
6. 通过后缀位移位x或y得到公共前缀，这是共同的祖先。

` `// Assuming that `BinaryNode_t` has `getData()`, `getLeft()` and `getRight()` class LowestCommonAncestor { typedef char type; // Data members which would behave as place holders const BinaryNode_t* m_pLCA; type m_Node1, m_Node2; static const unsigned int TOTAL_NODES = 2; // The core function which actually finds the LCA; It returns the number of nodes found // At any point of time if the number of nodes found are 2, then it updates the `m_pLCA` and once updated, we have found it! unsigned int Search (const BinaryNode_t* const pNode) { if(pNode == 0) return 0; unsigned int found = 0; found += (pNode->getData() == m_Node1); found += (pNode->getData() == m_Node2); found += Search(pNode->getLeft()); // below condition can be after this as well found += Search(pNode->getRight()); if(found == TOTAL_NODES && m_pLCA == 0) m_pLCA = pNode; // found ! return found; } public: // Interface method which will be called externally by the client const BinaryNode_t* Search (const BinaryNode_t* const pHead, const type node1, const type node2) { // Initialize the data members of the class m_Node1 = node1; m_Node2 = node2; m_pLCA = 0; // Find the LCA, populate to `m_pLCANode` and return (void) Search(pHead); return m_pLCA; } };` `

` `LowestCommonAncestor lca; BinaryNode_t* pNode = lca.Search(pWhateverBinaryTreeNodeToBeginWith); if(pNode != 0) ...` `

find最低公共祖先最简单的方法是使用以下algorithm：

```检查根节点

检查左子树

检查右子树

返回根
```
` `public int LCA(TreeNode root, int value 1, int value 2) { while (root != null) { if (value1 < root.data && value2 < root.data) return LCA(root.left, value1, value2); else if (value2 > root.data && value2 2 root.data) return LCA(root.right, value1, value2); else return root } return null; }` `

1. 取下
2. 以预购
3. 采取后置

postorder => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,​​12,7预订=> 7,3,1,0,2,6,4 ，5,12,9,8,11,10,13,15,14

• 例如：1

8,11最不共同的祖先

9是第一个常用的数字，在后序8和11之后，在8和11之前，因此9是答案

• 例如：2

5,10最不共同的祖先

11,9,14,15,13,​​12,7预购7,3,1,0,2,6,4

7是5,10之后的第一个数字，5,10之前在前，因此7是答案

1. find第一个节点的路线，将其存储到arr1。
2. 开始查找2节点的路由，同时检查从根到arr1的每个值。
3. 价值不同的时候退出。 旧的匹配值是LCA。

1. 在二叉树中查找LCA的recursion版本（O（N） – 至多访问每个节点）（解决scheme的要点是LCA是（a）二叉树中仅两个元素位于子树的任一侧的节点（左（右）是LCA （b）也不pipe哪一个节点在哪一边 – 最初我试图保留这个信息，显然recursion函数变得如此混乱，一旦我意识到它，就变得非常优雅。

2. search两个节点（O（N）），并跟踪path（使用额外的空间 – 所以，＃1可能是优越的，即使认为如果二叉树平衡良好，那么空间可能可以忽略不计，因为额外的内存消耗只是在为O（log（N））。

以便比较path（本质上与接受的答案类似），但path是通过假定指针节点不存在于二叉树节点中来计算的）

3. 为了完成（ 与问题无关 ），BST中的LCA（O（log（N））

4. testing

recursion：

` `private BinaryTreeNode LeastCommonAncestorUsingRecursion(BinaryTreeNode treeNode, int e1, int e2) { Debug.Assert(e1 != e2); if(treeNode == null) { return null; } if((treeNode.Element == e1) || (treeNode.Element == e2)) { //we don't care which element is present (e1 or e2), we just need to check //if one of them is there return treeNode; } var nLeft = this.LeastCommonAncestorUsingRecursion(treeNode.Left, e1, e2); var nRight = this.LeastCommonAncestorUsingRecursion(treeNode.Right, e1, e2); if(nLeft != null && nRight != null) { //note that this condition will be true only at least common ancestor return treeNode; } else if(nLeft != null) { return nLeft; } else if(nRight != null) { return nRight; } return null; }` `

` `public BinaryTreeNode LeastCommonAncestorUsingRecursion(int e1, int e2) { var n = this.FindNode(this._root, e1); if(null == n) { throw new Exception("Element not found: " + e1); } if (e1 == e2) { return n; } n = this.FindNode(this._root, e2); if (null == n) { throw new Exception("Element not found: " + e2); } var node = this.LeastCommonAncestorUsingRecursion(this._root, e1, e2); if (null == node) { throw new Exception(string.Format("Least common ancenstor not found for the given elements: {0},{1}", e1, e2)); } return node; }` `

` `public BinaryTreeNode LeastCommonAncestorUsingPaths(int e1, int e2) { var path1 = new List<BinaryTreeNode>(); var node1 = this.FindNodeAndPath(this._root, e1, path1); if(node1 == null) { throw new Exception(string.Format("Element {0} is not found", e1)); } if(e1 == e2) { return node1; } List<BinaryTreeNode> path2 = new List<BinaryTreeNode>(); var node2 = this.FindNodeAndPath(this._root, e2, path2); if (node1 == null) { throw new Exception(string.Format("Element {0} is not found", e2)); } BinaryTreeNode lca = null; Debug.Assert(path1[0] == this._root); Debug.Assert(path2[0] == this._root); int i = 0; while((i < path1.Count) && (i < path2.Count) && (path2[i] == path1[i])) { lca = path1[i]; i++; } Debug.Assert(null != lca); return lca; }` `

FindNodeAndPath被定义为

` `private BinaryTreeNode FindNodeAndPath(BinaryTreeNode node, int e, List<BinaryTreeNode> path) { if(node == null) { return null; } if(node.Element == e) { path.Add(node); return node; } var n = this.FindNodeAndPath(node.Left, e, path); if(n == null) { n = this.FindNodeAndPath(node.Right, e, path); } if(n != null) { path.Insert(0, node); return n; } return null; }` `

BST（LCA） – 无关（仅供参考）

` `public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2) { //ensure both elements are there in the bst var n1 = this.BstFind(e1, throwIfNotFound: true); if(e1 == e2) { return n1; } this.BstFind(e2, throwIfNotFound: true); BinaryTreeNode leastCommonAcncestor = this._root; var iterativeNode = this._root; while(iterativeNode != null) { if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2)) { iterativeNode = iterativeNode.Left; } else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2)) { iterativeNode = iterativeNode.Right; } else { //ie; either iterative node is equal to e1 or e2 or in between e1 and e2 return iterativeNode; } } //control will never come here return leastCommonAcncestor; }` `

unit testing

` `[TestMethod] public void LeastCommonAncestorTests() { int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 }; int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22}; BinarySearchTree bst = new BinarySearchTree(); foreach (int e in a) { bst.Add(e); bst.Delete(e); bst.Add(e); } for(int i = 0; i < b.Length; i++) { var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]); Assert.IsTrue(n.Element == b[i]); var n1 = bst.LeastCommonAncestorUsingPaths(a[i], a[i + 1]); Assert.IsTrue(n1.Element == b[i]); Assert.IsTrue(n == n1); var n2 = bst.LeastCommonAncestorUsingRecursion(a[i], a[i + 1]); Assert.IsTrue(n2.Element == b[i]); Assert.IsTrue(n2 == n1); Assert.IsTrue(n2 == n); } }` `

` `GETLCA(BINARYTREE BT, NODE A, NODE B) IF Root==NIL return NIL ENDIF IF Root==A OR root==B return Root ENDIF Left = GETLCA (Root.Left, A, B) Right = GETLCA (Root.Right, A, B) IF Left! = NIL AND Right! = NIL return root ELSEIF Left! = NIL Return Left ELSE Return Right ENDIF` `

` `#include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <math.h> static inline int min (int a, int b) { return ((a < b) ? a : b); } static inline int max (int a, int b) { return ((a > b) ? a : b); } typedef struct node_ { int value; struct node_ * left; struct node_ * right; } node; #define MAX 12 int IN_ORDER[MAX] = {0}; int POST_ORDER[MAX] = {0}; createNode(int value) { node * temp_node = (node *)malloc(sizeof(node)); temp_node->left = temp_node->right = NULL; temp_node->value = value; return temp_node; } node * insert(node * root, int value) { if (!root) { return createNode(value); } if (root->value > value) { root->left = insert(root->left, value); } else { root->right = insert(root->right, value); } return root; } /* Builds inorder traversal path in the IN array */ void inorder(node * root, int * IN) { static int i = 0; if (!root) return; inorder(root->left, IN); IN[i] = root->value; i++; inorder(root->right, IN); } /* Builds post traversal path in the POST array */ void postorder (node * root, int * POST) { static int i = 0; if (!root) return; postorder(root->left, POST); postorder(root->right, POST); POST[i] = root->value; i++; } int findIndex(int * A, int value) { int i = 0; for(i = 0; i< MAX; i++) { if(A[i] == value) return i; } } int CommonAncestor(int val1, int val2) { int in_val1, in_val2; int post_val1, post_val2; int j=0, i = 0; int max_index = -1; in_val1 = findIndex(IN_ORDER, val1); in_val2 = findIndex(IN_ORDER, val2); post_val1 = findIndex(POST_ORDER, val1); post_val2 = findIndex(POST_ORDER, val2); for (i = min(in_val1, in_val2); i<= max(in_val1, in_val2); i++) { for(j = 0; j < MAX; j++) { if (IN_ORDER[i] == POST_ORDER[j]) { if (j > max_index) { max_index = j; } } } } printf("\ncommon ancestor of %d and %d is %d\n", val1, val2, POST_ORDER[max_index]); return max_index; } int main() { node * root = NULL; /* Build a tree with following values */ //40, 20, 10, 30, 5, 15, 25, 35, 1, 80, 60, 100 root = insert(root, 40); insert(root, 20); insert(root, 10); insert(root, 30); insert(root, 5); insert(root, 15); insert(root, 25); insert(root, 35); insert(root, 1); insert(root, 80); insert(root, 60); insert(root, 100); /* Get IN_ORDER traversal in the array */ inorder(root, IN_ORDER); /* Get post order traversal in the array */ postorder(root, POST_ORDER); CommonAncestor(1, 100); }` `

There can be one more approach. However it is not as efficient as the one already suggested in answers.

• Create a path vector for the node n1.

• Create a second path vector for the node n2.

• Path vector implying the set nodes from that one would traverse to reach the node in question.

• Compare both path vectors. The index where they mismatch, return the node at that index – 1. This would give the LCA.

Cons for this approach:

Need to traverse the tree twice for calculating the path vectors. Need addtional O(h) space to store path vectors.

However this is easy to implement and understand as well.

Code for calculating the path vector:

` `private boolean findPathVector (TreeNode treeNode, int key, int pathVector[], int index) { if (treeNode == null) { return false; } pathVector [index++] = treeNode.getKey (); if (treeNode.getKey () == key) { return true; } if (findPathVector (treeNode.getLeftChild (), key, pathVector, index) || findPathVector (treeNode.getRightChild(), key, pathVector, index)) { return true; } pathVector [--index] = 0; return false; }` `

Try like this

` `node * lca(node * root, int v1,int v2) { if(!root) { return NULL; } if(root->data == v1 || root->data == v2) { return root;} else { if((v1 > root->data && v2 < root->data) || (v1 < root->data && v2 > root->data)) { return root; } if(v1 < root->data && v2 < root->data) { root = lca(root->left, v1, v2); } if(v1 > root->data && v2 > root->data) { root = lca(root->right, v1, v2); } } return root; }` `

Crude way:

• At every node
• X = find if either of the n1, n2 exist on the left side of the Node
• Y = find if either of the n1, n2 exist on the right side of the Node
• if the node itself is n1 || n2, we can call it either found on left or right for the purposes of generalization.
• If both X and Y is true, then the Node is the CA

The problem with the method above is that we will be doing the "find" multiple times, ie there is a possibility of each node getting traversed multiple times. We can overcome this problem if we can record the information so as to not process it again (think dynamic programming).

So rather than doing find every node, we keep a record of as to whats already been found.

Better Way:

• We check to see if for a given node if left_set (meaning either n1 | n2 has been found in the left subtree) or right_set in a depth first fashion. (NOTE: We are giving the root itself the property of being left_set if it is either n1 | n2)
• If both left_set and right_set then the node is a LCA.

` `struct Node * findCA(struct Node *root, struct Node *n1, struct Node *n2, int *set) { int left_set, right_set; left_set = right_set = 0; struct Node *leftCA, *rightCA; leftCA = rightCA = NULL; if (root == NULL) { return NULL; } if (root == n1 || root == n2) { left_set = 1; if (n1 == n2) { right_set = 1; } } if(!left_set) { leftCA = findCA(root->left, n1, n2, &left_set); if (leftCA) { return leftCA; } } if (!right_set) { rightCA= findCA(root->right, n1, n2, &right_set); if(rightCA) { return rightCA; } } if (left_set && right_set) { return root; } else { *set = (left_set || right_set); return NULL; } }` `

Code for A Breadth First Search to make sure both nodes are in the tree. Only then move forward with the LCA search. Please comment if you have any suggestions to improve. I think we can probably mark them visited and restart the search at a certain point where we left off to improve for the second node (if it isn't found VISITED)

` `public class searchTree { static boolean v1=false,v2=false; public static boolean bfs(Treenode root, int value){ if(root==null){ return false; } Queue<Treenode> q1 = new LinkedList<Treenode>(); q1.add(root); while(!q1.isEmpty()) { Treenode temp = q1.peek(); if(temp!=null) { q1.remove(); if (temp.value == value) return true; if (temp.left != null) q1.add(temp.left); if (temp.right != null) q1.add(temp.right); } } return false; } public static Treenode lcaHelper(Treenode head, int x,int y){ if(head==null){ return null; } if(head.value == x || head.value ==y){ if (head.value == y){ v2 = true; return head; } else { v1 = true; return head; } } Treenode left = lcaHelper(head.left, x, y); Treenode right = lcaHelper(head.right,x,y); if(left!=null && right!=null){ return head; } return (left!=null) ? left:right; } public static int lca(Treenode head, int h1, int h2) { v1 = bfs(head,h1); v2 = bfs(head,h2); if(v1 && v2){ Treenode lca = lcaHelper(head,h1,h2); return lca.value; } return -1; } }` `

You are correct that without a parent node, solution with traversal will give you O(n) time complexity.

Traversal approach Suppose you are finding LCA for node A and B, the most straightforward approach is to first get the path from root to A and then get the path from root to B. Once you have these two paths, you can easily iterate over them and find the last common node, which is the lowest common ancestor of A and B.

Recursive solution Another approach is to use recursion. First, we can get LCA from both left tree and right tree (if exists). If the either of A or B is the root node, then the root is the LCA and we just return the root, which is the end point of the recursion. As we keep divide the tree into sub-trees, eventually, we'll hit either A and B.

To combine sub-problem solutions, if LCA(left tree) returns a node, we know that both A and B locate in left tree and the returned node is the final result. If both LCA(left) and LCA(right) return non-empty nodes, it means A and B are in left and right tree respectively. In this case, the root node is the lowest common node.

Check Lowest Common Ancestor for detailed analysis and solution.

Some of the solutions here assumes that there is reference to the root node, some assumes that tree is a BST. Sharing my solution using hashmap, without reference to `root` node and tree can be BST or non-BST:

` ` var leftParent : Node? = left var rightParent : Node? = right var map = [data : Node?]() while leftParent != nil { map[(leftParent?.data)!] = leftParent leftParent = leftParent?.parent } while rightParent != nil { if let common = map[(rightParent?.data)!] { return common } rightParent = rightParent?.parent }` `

The code in Php. I've assumed the tree is an Array binary tree. Therefore, you don't even require the tree to calculate the LCA. input: index of two nodes output: index of LCA

` ` <?php global \$Ps; function parents(\$l,\$Ps) { if(\$l % 2 ==0) \$p = (\$l-2)/2; else \$p = (\$l-1)/2; array_push(\$Ps,\$p); if(\$p !=0) parents(\$p,\$Ps); return \$Ps; } function lca(\$n,\$m) { \$LCA = 0; \$arr1 = array(); \$arr2 = array(); unset(\$Ps); \$Ps = array_fill(0,1,0); \$arr1 = parents(\$n,\$arr1); unset(\$Ps); \$Ps = array_fill(0,1,0); \$arr2 = parents(\$m,\$arr2); if(count(\$arr1) > count(\$arr2)) \$limit = count(\$arr2); else \$limit = count(\$arr1); for(\$i =0;\$i<\$limit;\$i++) { if(\$arr1[\$i] == \$arr2[\$i]) { \$LCA = \$arr1[\$i]; break; } } return \$LCA;//this is the index of the element in the tree } var_dump(lca(5,6)); ?>` `

Do tell me if there are any shortcomings.

//If both the values are less than the current node then traverse the left subtree //Or If both the values are greater than the current node then traverse the right subtree //Or LCA is the current node

` `public BSTNode findLowestCommonAncestor(BSTNode currentRoot, int a, int b){ BSTNode commonAncestor = null; if (currentRoot == null) { System.out.println("The Tree does not exist"); return null; } int currentNodeValue = currentRoot.getValue(); //If both the values are less than the current node then traverse the left subtree //Or If both the values are greater than the current node then traverse the right subtree //Or LCA is the current node if (a < currentNodeValue && b < currentNodeValue) { commonAncestor = findLowestCommonAncestor(currentRoot.getLeft(), a, b); } else if (a > currentNodeValue && b > currentNodeValue) { commonAncestor = findLowestCommonAncestor(currentRoot.getRight(), a, b); } else { commonAncestor = currentRoot; } return commonAncestor; }` `
• 混淆一个ID
• ASCII艺术图像转换algorithm如何工作？
• 最适合的调度algorithm
• Eratosthenes的分割筛？
• 编写一个将文本作为input的程序，并生成一个能够再现该文本的程序
• 从元素有权重的列表中selectk个随机元素
• 将recursionalgorithm转换为迭代algorithm的devise模式
• 使用一组素数按升序生成整数
• 什么是最好的自动完成/build议algorithm，数据结构
• 这个游戏背后的math/计算原理是什么？
• 快速algorithm绘制实心圆？