|
题目及测试
package sword050;
/*题目：求树中两个结点的最低公共祖先
*/
public class main {
public static void main(String[] args) {
Object[] x=new Object[]{3,5,1,6,2,0,8,null,null,7,4};
BinaryTree tree=new BinaryTree(x);
tree.printTree(tree.root);
test(tree.root,tree.root.left,tree.root.right);
test(tree.root,tree.root.left,tree.root.left.right.right);
}
private static void test(TreeNode ito,TreeNode ito2,TreeNode ito3) {
Solution solution = new Solution();
TreeNode rtn;
long begin = System.currentTimeMillis();
rtn = solution.lowestCommonAncestor(ito,ito2,ito3);//执行程序
long end = System.currentTimeMillis();
System.out.println("rtn=" );
System.out.print(rtn.val);
System.out.println();
System.out.println("耗时：" + (end - begin) + "ms");
System.out.println("-------------------");
}
}
解法1（成功）
如果是二叉搜索树的话，我们只需从根结点判断，如果二结点与根的左右子树比较一大一小，那么跟结点就是二者最低公共祖先；如果二结点都比左子结点小，向左子树递归进行比较；如果二结点都比右子树结点大，向右子树递归进行比较；
如果不是二叉搜索树，但带有指向父节点的指针，那么此题转换成在两个有相交的链表上求第一个相交点。
如果不带指向父节点的指针，那么我们可以记录从根结点到这两个结点的路径即可求出。
package sword050;
import java.util.HashSet;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
HashSet<TreeNode> pParent = new HashSet<TreeNode>();
HashSet<TreeNode> qParent = new HashSet<TreeNode>();
pParent.add(p);
qParent.add(q);
while(true) {
if(qParent.contains(p)) {
return p;
}else {
if(p != root) {
p = p.parent;
pParent.add(p);
}
}
if(pParent.contains(q)) {
return q;
}else {
if(q != root) {
q = q.parent;
qParent.add(q);
}
}
}
}
}
| 
转播
