| 9 | |
| 10 | // Checks how many �special� nodes are located under this root |
| 11 | public static int covers(TreeNode root, TreeNode p, TreeNode q) { |
| 12 | int ret = NO_NODES_FOUND; |
| 13 | if (root == null) return ret; |
| 14 | if (root == p || root == q) ret += 1; |
| 15 | ret += covers(root.left, p, q); |
| 16 | if(ret == TWO_NODES_FOUND) // Found p and q |
| 17 | return ret; |
| 18 | return ret + covers(root.right, p, q); |
| 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; |