| 13 | } |
| 14 | |
| 15 | public static Result commonAncestorHelper(TreeNode root, TreeNode p, TreeNode q) { |
| 16 | if (root == null) { |
| 17 | return new Result(null, false); |
| 18 | } |
| 19 | if (root == p && root == q) { |
| 20 | return new Result(root, true); |
| 21 | } |
| 22 | |
| 23 | Result rx = commonAncestorHelper(root.left, p, q); |
| 24 | if (rx.isAncestor) { // Found common ancestor |
| 25 | return rx; |
| 26 | } |
| 27 | |
| 28 | Result ry = commonAncestorHelper(root.right, p, q); |
| 29 | if (ry.isAncestor) { // Found common ancestor |
| 30 | return ry; |
| 31 | } |
| 32 | |
| 33 | if (rx.node != null && ry.node != null) { |
| 34 | return new Result(root, true); // This is the common ancestor |
| 35 | } else if (root == p || root == q) { |
| 36 | /* If we�re currently at p or q, and we also found one of those |
| 37 | * nodes in a subtree, then this is truly an ancestor and the |
| 38 | * flag should be true. */ |
| 39 | boolean isAncestor = rx.node != null || ry.node != null; |
| 40 | return new Result(root, isAncestor); |
| 41 | } else { |
| 42 | return new Result(rx.node != null ? rx.node : ry.node, false); |
| 43 | } |
| 44 | } |
| 45 | |
| 46 | public static TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) { |
| 47 | Result r = commonAncestorHelper(root, p, q); |