树中两个节点的最低公共祖先
以下几个方法中会用到的方法和类：
class BinaryTreeNode {
int data;
BinaryTreeNode left;
BinaryTreeNode right;
BinaryTreeNode parent;
public BinaryTreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
}
}
/**
* 中序遍历
* @param root
*/
public static void LDR(BinaryTreeNode root) {
if(root != null) {
LDR(root.left);
show(root);
LDR(root.right);
}
}
/**
* 打印
* @param root
*/
private static void show(BinaryTreeNode root) {
System.out.print(root.data+"\t");
}
1、当树是二叉搜索树时：
二叉搜索树是排序过的，左子节点都比父节点小，右子节点都比父节点大；当树是二叉搜索树时，我们只需要从根节点开始和输入的两个节点相比较：
①当前节点的值位于输入的两个节点的值之间，那么当前节点就是最低公共祖先；
②当前节点的值比输入的两个节点的值都大，那么最低公共祖先节点在当前节点的左子树中，去当前节点的左子树中查找；
③当前节点的值比输入的两个节点的值都小，那么最低公共祖先节点在当前节点的右子树中，去当前节点的右子树中查找；
/**
* 当树是二叉搜索树时：
* @param root
* @param node1
* @param node2
* @return
*/
public static BinaryTreeNode minimum_commonality_ancestor(
BinaryTreeNode root, BinaryTreeNode node1,BinaryTreeNode node2) {
if(root == null || node1 == null || node2 == null) {
return null;
}
BinaryTreeNode ancestor = null;
if((node1.data > root.data && node2.data < root.data)
|| (node2.data > root.data && node1.data < root.data)) {
ancestor = root;
}
if(node1.data > root.data && node2.data > root.data && root.right != null) {
ancestor = minimum_commonality_ancestor(root.right,node1,node2);
}
if(node1.data < root.data && node2.data < root.data && root.left != null) {
ancestor = minimum_commonality_ancestor(root.left,node1,node2);
}
return ancestor;
}
2、当树中有指向父节点的指针的时候：
这时该问题可以转化为求两个链表的第一个公共节点：
（在这里的代码还是二叉树，道理是一样的）：
/**
* 有指向父节点指针的时候
* @param root
* @param node1
* @param node2
* @return
*/
public static BinaryTreeNode minimum_commonality_ancestor1(
BinaryTreeNode root, BinaryTreeNode node1,BinaryTreeNode node2) {
if (root == null || node1 == null || node2 == null) {
return null;
}
BinaryTreeNode cur1 = node1;
BinaryTreeNode cur2 = node2;
int length = getLength(node1)-getLength(node2);
if(length < 0) {
length = -length;
cur1 = node2;
cur2 = node1;
}
while (length > 0) {
cur1 = cur1.parent;
length--;
}
while (cur1.parent != null) {
if(cur1 == cur2) {
break;
}
cur1 = cur1.parent;
cur2 = cur2.parent;
}
return cur1;
}
/**
* 得到指定叶节点到根节点的长度
* @param node
* @return
*/
public static int getLength(BinaryTreeNode node) {
if(node == null) {
throw new NullPointerException("参数为空！");
}
BinaryTreeNode cur = node;
int length = 0;
while (cur.parent != null) {
cur = cur.parent;
length++;
}
return length;
}
3、通用做法：
先分别得到从根节点到输入节点的路径，路径用栈存起来，然后比较两条路径，得到这两条路径的第一个相同的节点，就是最低公共祖先节点：
（在这里的代码依旧是二叉树）：
/**
* 通用做法
* @param root
* @param node1
* @param node2
* @return
*/
public static BinaryTreeNode minimum_commonality_ancestor2(
BinaryTreeNode root, BinaryTreeNode node1,BinaryTreeNode node2) {
if (root == null || node1 == null || node2 == null) {
return null;
}
Stack<BinaryTreeNode> stack1 = new Stack<>();
Stack<BinaryTreeNode> stack2 = new Stack<>();
boolean[] sign = new boolean[1];
path(root,node1,stack1,sign);
sign[0] = false;
path(root,node2,stack2,sign);
BinaryTreeNode node = seek(stack1,stack2);
return node;
}
/**
* 得到两个路径的第一个公共节点
* @param stack1
* @param stack2
* @return
*/
private static BinaryTreeNode seek(Stack<BinaryTreeNode> stack1, Stack<BinaryTreeNode> stack2) {
if(stack1 == null || stack2 == null) {
return null;
}
int length = stack1.size()-stack2.size();
if(length < 0) {
length = -length;
while (length > 0) {
length--;
stack2.pop();
}
}else {
while (length > 0) {
length--;
stack1.pop();
}
}
boolean flag = false;
BinaryTreeNode cur = null;
while (!flag) {
if(stack1.peek() == stack2.peek()) {
flag = true;
cur = stack1.peek();
}
stack1.pop();
stack2.pop();
}
return cur;
}
/**
* 得到路径
* @param root
* @param node
* @param stack
* @param sign
*/
private static void path(BinaryTreeNode root, BinaryTreeNode node,
Stack<BinaryTreeNode> stack,boolean[] sign) {
if(sign[0]) {
return;
}
boolean flag = false;
if(root == node) {
stack.push(root);
sign[0] = true;
return;
}else {
stack.push(root);
if (root.left != null) {
path(root.left, node, stack, sign);
}
if (!sign[0] && root.right != null) {
flag = true;
stack.pop();
path(root.right, node, stack, sign);
}
if(!sign[0] && flag) {
stack.pop();
}
}
}
测试代码：
1、当树是二叉搜索树时：
public static void main(String[] args) {
BinaryTreeNode root = new BinaryTreeNode(4);
BinaryTreeNode cur1 = root,cur2;
cur1.left = new BinaryTreeNode(2);
cur1.right = new BinaryTreeNode(6);
cur2 = cur1.right;
cur1 = cur1.left;
cur1.left = new BinaryTreeNode(1);
cur1.right = new BinaryTreeNode(3);
cur2.left = new BinaryTreeNode(5);
cur2.right = new BinaryTreeNode(7);
LDR(root);
System.out.println();
show(minimum_commonality_ancestor(root,cur1.right,cur2));
}
运行结果：
1 2 3 4 5 6 7
4
2、当树有指向父节点的指针时;
public static void main(String[] args) {
BinaryTreeNode root = new BinaryTreeNode(1);
BinaryTreeNode cur1 = root,cur2;
cur1.left = new BinaryTreeNode(2);
cur1.right = new BinaryTreeNode(3);
cur1.left.parent = cur1;
cur1.right.parent = cur1;
cur1 = cur1.left;
cur1.left = new BinaryTreeNode(4);
cur1.right = new BinaryTreeNode(5);
cur1.left.parent = cur1;
cur1.right.parent = cur1;
cur2 = cur1.right;
cur1 = cur1.left;
cur1.left = new BinaryTreeNode(6);
cur1.right = new BinaryTreeNode(7);
cur1.left.parent = cur1;
cur1.right.parent = cur1;
cur2.left = new BinaryTreeNode(8);
cur2.right = new BinaryTreeNode(9);
cur2.left.parent = cur2;
cur2.right.parent = cur2;
show(minimum_commonality_ancestor1(root,cur1.left, cur2));
运行结果：
2
3、通用：
public static void main(String[] args) {
BinaryTreeNode root = new BinaryTreeNode(1);
BinaryTreeNode cur1 = root,cur2;
cur1.left = new BinaryTreeNode(2);
cur1.right = new BinaryTreeNode(3);
cur1 = cur1.left;
cur1.left = new BinaryTreeNode(4);
cur1.right = new BinaryTreeNode(5);
cur2 = cur1.right;
cur1 = cur1.left;
cur1.left = new BinaryTreeNode(6);
cur1.right = new BinaryTreeNode(7);
cur2.left = new BinaryTreeNode(8);
cur2.right = new BinaryTreeNode(9);
TestDemo29.print1(root);
show(minimum_commonality_ancestor2(root,cur1,cur2.right));
}
运行结果：
2