| 19 | } |
| 20 | |
| 21 | public static TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) { |
| 22 | if (q == p && (root.left == q || root.right == q)) return root; |
| 23 | int nodesFromLeft = covers(root.left, p, q); // Check left side |
| 24 | if (nodesFromLeft == TWO_NODES_FOUND) { |
| 25 | if(root.left == p || root.left == q) return root.left; |
| 26 | else return commonAncestor(root.left, p, q); |
| 27 | } else if (nodesFromLeft == ONE_NODE_FOUND) { |
| 28 | if (root == p) return p; |
| 29 | else if (root == q) return q; |
| 30 | } |
| 31 | |
| 32 | int nodesFromRight = covers(root.right, p, q); // Check right side |
| 33 | if(nodesFromRight == TWO_NODES_FOUND) { |
| 34 | if(root.right == p || root.right == q) return root.right; |
| 35 | else return commonAncestor(root.right, p, q); |
| 36 | } else if (nodesFromRight == ONE_NODE_FOUND) { |
| 37 | if (root == p) return p; |
| 38 | else if (root == q) return q; |
| 39 | } |
| 40 | if (nodesFromLeft == ONE_NODE_FOUND && |
| 41 | nodesFromRight == ONE_NODE_FOUND) return root; |
| 42 | else return null; |
| 43 | } |
| 44 | |
| 45 | public static void main(String[] args) { |
| 46 | int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; |