|
树中两个结点的最低公共祖先 代码实现：
package case50_GetLastCommonNode;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
/**
* 题目：输入树的两个结点，求他们的最低公共祖先。
*
* @author WangSai
*
*/
public class GetLastCommonNode {
/**
* 1>:若树是二叉搜索树，则可以根据这个两个结点和二叉搜索的的特点遍历完成。
*
* @param root,二叉树的根节点
* @param node1，二叉树中的指定节点
* @param node2，二叉树中的指定节点
* @return 二叉树中的最低公共祖先
*/
private TreeNode getMyNode1(TreeNode root, TreeNode node1, TreeNode node2) {
// 异常值检测
if (root == null)
return null;
// 递归调用，判断。
// 当树中当前节点的值大于node1和node2的值得时候，最低公共祖先在左子节点中。
if (root.data > node1.data && root.data > node2.data) {
return getMyNode1(root.lchild, node1, node2);
}
// 当树中当前节点的值小于node1和node2的值得时候，最低公共祖先在右子节点中。
else if (root.data < node1.data && root.data < node2.data) {
return getMyNode1(root.rchild, node1, node2);
}
// 当树中当前节点的值介于node1和node2的值之间的时候，该节点就是最低公共祖先。
else if ((root.data >= node1.data && root.data <= node2.data)
|| (root.data <= node1.data && root.data >= node2.data)) {
return root;
}
return null;
}
/**
* 2>:若树是普通树，但是有指向父节点的parent指针。这种问题可以转换成求链表的第一个公共节点的问题。
*
* @param root,二叉树的根节点
* @param node1，二叉树中的指定节点
* @param node2，二叉树中的指定节点
* @return 二叉树中的最低公共祖先
*/
private TreeNode getMyNode2(TreeNode root, TreeNode node1, TreeNode node2) {
if (root == null)
return null;
// 创建辅助栈1
Stack<TreeNode> stack1 = new Stack<TreeNode>();
while (node1 != null) {
stack1.push(node1);
node1 = node1.parent;
}
// 创建辅助栈2
Stack<TreeNode> stack2 = new Stack<TreeNode>();
while (node2 != null) {
stack2.push(node2);
node2 = node2.parent;
}
while (stack1.size() > 0 && stack2.size() > 0) {
TreeNode tmp1 = stack1.pop();
TreeNode tmp2 = stack2.pop();
if (tmp2.data == tmp1.data) {
return tmp1;
}
}
return null;
}
/**
* 3>:若树是普通树，没有指向父节点的parent指针。我们可以从头根节点开始遍历，然后把包含node1和node2节点的路径保存下来。然后，
* 可以转换成求链表的第一个公共节点的问题。
*
* @param root,二叉树的根节点
* @param node1，二叉树中的指定节点
* @param node2，二叉树中的指定节点
* @return 二叉树中的最低公共祖先
*/
private static TreeNode getMyNode3(TreeNode root, TreeNode node1, TreeNode node2) {
// 异常值检测
if (root == null)
return null;
// 辅助空间保存包含node1的路径
ArrayList<TreeNode> list1 = new ArrayList<TreeNode>();
// 辅助空间保存包含node2的路径
ArrayList<TreeNode> list2 = new ArrayList<TreeNode>();
// 寻找存在node1在以root为根节点的树中的路径
findPath(root, node1, list1);
// 寻找存在node2在以root为根节点的树中的路径
findPath(root, node2, list2);
// 把list1中保存的节点入栈
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Iterator<TreeNode> ite1 = list1.iterator();
while (ite1.hasNext()) {
stack1.push(ite1.next());
}
// 把list2中保存的节点入栈
Stack<TreeNode> stack2 = new Stack<TreeNode>();
Iterator<TreeNode> ite2 = list2.iterator();
while (ite2.hasNext()) {
stack2.push(ite2.next());
}
while (!stack1.isEmpty() && !stack2.isEmpty()) {
TreeNode n1 = stack1.pop();
TreeNode n2 = stack2.pop();
if (n1 == n2)
return n1;
}
return null;
}
/**
* 以root为根节点的树包含node节点的路径。
*
* @param root,树的根节点
* @param node，树中的节点
* @param list,保存包含node1的路径
*/
private static void findPath(TreeNode root, TreeNode node, ArrayList<TreeNode> list) {
if (root == null)
return;
list.add(root);
if (root != node) {
if (root.lchild == null && root.rchild == null && root.mchild == null) {
list.remove(list.size() - 1);
return;
} else {
findPath(root.lchild, node, list);
for (TreeNode temp : list) {
if (temp == node)
return;
}
findPath(root.rchild, node, list);
for (TreeNode temp : list) {
if (temp == node)
return;
}
findPath(root.mchild, node, list);
for (TreeNode temp : list) {
if (temp == node)
return;
}
list.remove(list.size() - 1);
}
} else if (root == node) {
return;
}
}
public static void main(String[] args) {
test1();
test2();
}
/**
* 普通二叉树
* ..............1..............................................................
* ........../.......\...........................................................
* .........2.........3..........................................................
* ......./..\......./..\.........................................................
* ......4...5......6....7.......................................................
* ...../.../..\......./.|.\....................................................
* ....8...12..9......13.10.11...................................................
*/
private static void test1() {
TreeNode root = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
TreeNode n8 = new TreeNode(8);
TreeNode n9 = new TreeNode(9);
TreeNode n10 = new TreeNode(10);
TreeNode n11 = new TreeNode(11);
TreeNode n12 = new TreeNode(12);
TreeNode n13 = new TreeNode(13);
root.lchild = n2;
root.rchild = n3;
n2.lchild = n4;
n2.rchild = n5;
n3.lchild = n6;
n3.rchild = n7;
n4.lchild = n8;
n5.rchild = n9;
n5.lchild = n12;
n7.rchild = n11;
n7.lchild = n13;
n7.mchild = n10;
System.out.print("普通二叉树，最低公共祖先为 1 ：");
TreeNode node1 = getMyNode3(root, n8, n11);
System.out.println(node1.data);
System.out.print("普通树，最低公共祖先为 7 ：");
TreeNode node2 = getMyNode3(root, n13, n11);
System.out.println(node2.data);
System.out.print("普通树n11为树中的节点，另一个节点为null，最低公共祖先为 null ：");
TreeNode node3 = getMyNode3(root, null, n11);
System.out.println(node3);
}
/**
* 退化二叉树
* ..............1..............................................................
* ........../..................................................................
* .........2...................................................................
* ......./......................................................................
* ......4.......................................................................
* ...../.......................................................................
* ....8.........................................................................
*/
private static void test2() {
TreeNode root = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n4 = new TreeNode(4);
TreeNode n8 = new TreeNode(8);
root.lchild = n2;
n2.lchild = n4;
n2.rchild = n8;
System.out.print("退化为斜树，最低公共祖先为 2 ：");
TreeNode node1 = getMyNode3(root, n8, n4);
System.out.println(node1.data);
}
}
树中节点结构的定义：
package case50_GetLastCommonNode;
/**
* 二叉树的节点结构定义
*
* @author WangSai
*
*/
public class TreeNode {
int data;
TreeNode lchild;
TreeNode rchild;
TreeNode mchild;
TreeNode parent;
public TreeNode() {
}
public TreeNode(int data) {
this.data = data;
}
}
| 
转播
