How to implement a minimal common ancestor for a binary tree using Java?

Question

I came across the following implementation and spent some time, but still can not understand this idea. Can someone explain line by line what he is doing? I just don't understand at what point it can decide that node is the ancestor.

thanks

public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if(left != null && right != null) return root; return left != null ? left : right; } } 

Answer 1

The main idea of ​​marking the presence of a number in a tree branch is to use a non-zero pointer for the FOUND number and a null pointer for NOTFOUND.

The call column goes back when a number ( p or q ) is found, or when root is null . Later, a clear indication of the absence of the desired number is given.

There are four possible scenarios:

1.) And under one parent.

  root / \ Leftsubtree Rightsubtree p/qq/p 

In this case, in the code below, the moment will come when it will be done if(left != null && right != null) return root;

2.) One parent of the other.

  q/pp/q / OR \ Leftsubtree Rightsubtree p/qq/p 

In this case, this will be done if(root == null || root == p || root == q) return root;

3.) Or they are not present in the tree. This condition will be undetected . As shown in case No. 2, the function immediately returns without further movement and looks for its copy in the tree below.

4.) None of them are present in the tree.

The first line if(root == null ... return ; will be executed for each non-existent child. The final result will be null return, since none of the numbers will be found.

---

Explanation by line.

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null || root == p || root == q) return root; /* (root == null) This proves that root is not in the branch of tree of our interest. Returning null would means NOTFOUND.*/ /* (root == p || root == q) either p or q or both are found. Returning non-null root would means FOUND. */ /*Check for presence in leftsubtree */ TreeNode left = lowestCommonAncestor(root.left, p, q); /*Check for presence in rightsubtree */ TreeNode right = lowestCommonAncestor(root.right, p, q); /* root / \ leftsubtree Rightsubtree p/qq/p */ if(left != null && right != null) return root; //both the numbers are found inside tree under root // left or right subtree OR both don't have p or q. Return the overall find result under root. return left != null ? left : right; } 

Answer 2

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // root == null (no root no LCA) // root == p || root == q (if either p or q is the root then root is LCA) if(root == null || root == p || root == q) return root; //get the LCA of p and q in left sub tree TreeNode left = lowestCommonAncestor(root.left, p, q); //get the LCA of p and q in right sub tree TreeNode right = lowestCommonAncestor(root.right, p, q); // if one of p or q is in left subtree and another is in the right subtree, //then the root is the LCA if(left != null && right != null) return root; // if left is not null, left is LCA, else right is LCA return left != null ? left : right; } 

Answer 3

 if(root == null || root == p || root == q) return root; 

if the current root node null , then common ancestor p and q do not exist in the current sub_tree, so return null root==null

and if p or q is root . I assume that p = root and here, as for q , it is either offspring p or not offspring p , however , in the case of there is no need to trace sub_tree from p , as if the previous case p was the ancestor of q so just return pp == root , otherwise return p directly, this will not lead to an error, although in this case p is not ancestor of q .
for approval
if(left != null && right != null) return root; and I will explain it later.

  TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); 

Now there are several possible things:
1.p and q are all offspring root.left
2. p and q are all offspring of root.right
3. these two node one offspring from root.left another offspring from root.right

---

these two recursive statement are used to find common ancestor p and q ( for 1,2 ) else is used to find p and q ( for 3 )

---

 if(left != null && right != null) return root; 

this operator is used to handle the corresponding result 3 , p and q there are left_subtree and right_suntree from the root, so ancestor is root

---

  return left != null ? left : right; 

this operator is used to process corresponding result 1,2 , p and q the same sub_tree exists both on the left and on the right.

Answer 4

 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL || root->val == p->val || root->val == q->val || (p->val < root->val && root->val < q->val) || (q->val < root->val && root->val < p->val)) { return root; } else if (root->val < p->val) return lowestCommonAncestor(root-> right, p, q); else return lowestCommonAncestor(root->left, p, q); 

Here is my answer in C ++, but should be very similar while you switch '->' to '.' syntax. This is a recursive function in which it checks the current sheet with its left and right children, and as soon as the conditions of the first if condition are true, this means that he identified the lowest common ancestor, because if one of his children is larger, it means That is the smallest cost.

For example: given 2 as its root and 1 and 4 as its children (left and right, respectively), 1 is less than the root, but 4 is not, therefore 2 is the smallest common denominator. IT will stop at the first start.

If you draw yourself a binary tree and test each step, it will make more sense.