获取二叉树中两个节点的最近公共祖先
//二叉树节点对象public class TreeNode{ private TreeNode left = null; private TreeNode right = null; private int data = 0; public TreeNode getLeft(){ return left; } public TreeNode getRight(){ return right; } public int getData(){ return data; } //获取最近公共祖先 public static TreeNode getNearestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){ if(root == null || p == null || q == null){ return null; }else{ if(contains(root.getLeft(), p)){ if(contains(root.getRight(), q)){ return root; }else{ return getNearestCommonAncestor(root.getLeft(), p, q); } }else{ if(contains(root.getRight(), q)){ return getNearestCommonAncestor(root.getRight(), p, q); }else{ return root; } } } } //给定的树root中是否包含节点p private static boolean contains(TreeNode root, TreeNode p){ if(root.getData() == p.getData()){ return true; }else{ return contains(root.getLeft(), p) || contains(root.getRight(), p); } }}
?
?
