三种情况：（自己写的，不保证所有实例完全通过）
1.树是二叉搜索树的情况；用搜索树的性质进行查找；
2.树是普通二叉树，但是包含父节点；用两个单链表的第一个公共父节点来进行查找；
3.树是多叉树，先用一个方法找到两个节点从根结点到各个节点的路径，在用两个单链表的第一个公共父节点来进行查找；
import java.util.LinkedList; import java.util.Stack; class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; } }
class TreeNodeWithMoreChild { public int val; public TreeNodeWithMoreChild first; public TreeNodeWithMoreChild second; public TreeNodeWithMoreChild third; public TreeNodeWithMoreChild(int val) { this.val = val; } }
class TreeNodeWithMoreChild { public int val; public TreeNodeWithMoreChild first; public TreeNodeWithMoreChild second; public TreeNodeWithMoreChild third; public TreeNodeWithMoreChild(int val) { this.val = val; } } public class FatherNodeForTree50 { /** * 是二叉排序树； * * @param left * @param right * @param root * @return */ public TreeNode getFatherNode(TreeNode left, TreeNode right, TreeNode root) { if(root == null || left == null || right == null) { return null; } else { if(root.val >= left.val && root.val <= right.val) { return root; } else if((root.val > left.val && root.val >= right.val) || (root.val >= left.val && root.val > right.val)) { return getFatherNode(left, right, root.left); } else { return getFatherNode(left, right, root.right); } } } /** * 带有指向父节点的指针的二叉树； * 等于求两个单链表的公共节点； * @param left * @param right * @param root * @return */ public TreeNodeWithFather getFatherNode2(TreeNodeWithFather left, TreeNodeWithFather right) { if(left == null || right == null) { return null; } else { int n1 = 0; int n2 = 0; TreeNodeWithFather p1 = left; TreeNodeWithFather p2 = right; while(p1.father != null) { n1++; p1= p1.father; } while(p2.father != null) { n2++; p2 = p2.father; } int sub = 0; p1 = left; p2 = right; int k = 0; if(n2 > n1) { sub = n2 - n1; while(k < sub) { p2 = p2.father; k++; } } else { k = 0; sub = n1 - n2; while(k < sub) { p1 = p1.father; k++; } } while(p1 != null && p2 != null && p1 != p2) { p1 = p1.father; p2 = p2.father; } if(p1 == null || p2 == null) { System.out.println("不存在公共节点"); return null; } else { return p1; } } } public boolean findTwoNode(TreeNodeWithMoreChild root, TreeNodeWithMoreChild curNode, Stack<TreeNodeWithMoreChild> path) { if(root == curNode) { return true; } else { path.push(root); boolean found = false; if(!found) { if(root.first != null) { found = findTwoNode(root.first, curNode, path); } if(!found && root.second != null) { found = findTwoNode(root.second, curNode, path); } if(!found && root.third != null) { found = findTwoNode(root.third, curNode, path); } } if(!found) { path.pop(); } return found; } } public TreeNodeWithMoreChild getFatherNode3(LinkedList<TreeNodeWithMoreChild> left, LinkedList<TreeNodeWithMoreChild> right) { if(left == null || right == null || left.isEmpty() || right.isEmpty()) { return null; } else { int n1 = left.size(); int n2 = right.size(); int sub = 0; if(n2 > n1) { sub = n2 - n1; for(int i = 0; i < n1; i++) { if(right.get(i + sub) == left.get(i)) { return left.get(i); } } } else { sub = n1 - n2; for(int i = 0; i < n2; i++) { if(left.get(i + sub) == right.get(i)) { return right.get(i); } } } return null; } } /** * 具有多个分支的树形结构； * 1.找路径； * 2.用单链表的公共节点找出父节点； * @param node1 * @param node2 * @param root * @return */
public TreeNodeWithMoreChild getCommonNode(TreeNodeWithMoreChild node1, TreeNodeWithMoreChild node2, TreeNodeWithMoreChild root) { if(root == null || node1 == null || node2 == null) { return null; } else { Stack<TreeNodeWithMoreChild> stack1 = new Stack<TreeNodeWithMoreChild>(); Stack<TreeNodeWithMoreChild> stack2 = new Stack<TreeNodeWithMoreChild>(); findTwoNode(root, node1, stack1); findTwoNode(root, node2, stack2); LinkedList<TreeNodeWithMoreChild> reversePath1 = new LinkedList<TreeNodeWithMoreChild>(); LinkedList<TreeNodeWithMoreChild> reversePath2 = new LinkedList<TreeNodeWithMoreChild>(); while(!stack1.isEmpty()) { reversePath1.offer(stack1.pop()); } while(!stack2.isEmpty()) { reversePath2.offer(stack2.pop()); } ///此处要写getFatherNode2(reversePath1, reversePath2); //因为与上面的getFatherNode2一致就不写了，但注意类型TreeNodeWithFather，此处是TreeNodeWithMoreChild； return getFatherNode3(reversePath1, reversePath2); } } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub TreeNode root = new TreeNode(13); TreeNode tn1 = new TreeNode(11); TreeNode tn2 = new TreeNode(14); TreeNode tn3 = new TreeNode(10); TreeNode tn4 = new TreeNode(12); root.left = tn1; root.right = tn2; tn1.left = tn3; tn1.right = tn4; FatherNodeForTree50 fnt = new FatherNodeForTree50(); TreeNode res = fnt.getFatherNode(tn4, tn2, root); System.out.println(res.val); TreeNodeWithFather rootl = new TreeNodeWithFather(5); TreeNodeWithFather left1 = new TreeNodeWithFather(15); TreeNodeWithFather left2 = new TreeNodeWithFather(25); TreeNodeWithFather left3 = new TreeNodeWithFather(35); TreeNodeWithFather rootr = new TreeNodeWithFather(54); TreeNodeWithFather right1 = new TreeNodeWithFather(55); left3.father = left2; left2.father = left1; left1.father = rootl; right1.father = rootr; rootr.father = rootl; TreeNodeWithFather r = fnt.getFatherNode2(left3, right1); System.out.println(r.val); TreeNodeWithMoreChild tn = new TreeNodeWithMoreChild(0); TreeNodeWithMoreChild tn11 = new TreeNodeWithMoreChild(1); TreeNodeWithMoreChild tn21 = new TreeNodeWithMoreChild(11); TreeNodeWithMoreChild tn31 = new TreeNodeWithMoreChild(12); TreeNodeWithMoreChild tn41 = new TreeNodeWithMoreChild(111); TreeNodeWithMoreChild tn5 = new TreeNodeWithMoreChild(112); TreeNodeWithMoreChild tn6 = new TreeNodeWithMoreChild(121); TreeNodeWithMoreChild tn7 = new TreeNodeWithMoreChild(1211); tn.first = tn11; tn11.first = tn21; tn11.second = tn31; tn21.first = tn41; tn21.second = tn5; tn31.first = tn6; tn6.first = tn7; TreeNodeWithMoreChild resss = fnt.getCommonNode(tn41, tn5, tn); System.out.println(resss.val); } }
