首页 > 代码库 > CTCI 4.7
CTCI 4.7
Design an algorithm and write code to find the first common ancestory of two nodes in a binary tree. Avoid storing additional nodes in data structure. NOTE: This is not necessarily a binary search tree.
/* use find() to determin whether the tree contains the two targets, if contains, update the result. Then tryto determine whether the two subtrees contains the targets. Since the first common ancestor would be the lastnode find to contain the targets, the latest result would just be what we want.*/public class FirstCommonAncestor { TreeNode res = null; public void fircomanc(TreeNode node, TreeNode tarA, TreeNode tarB) { if(find(node, tarA) == true && find(node, tarB) == true) res = node; if(node != null) { fircomanc(node.left, tarA, tarB); fircomanc(node.right, tarA, tarB); } } private boolean find(TreeNode node, TreeNode tar) { if(node == tar) return true; if(node != null) return (find(node.left, tar) | find(node.right, tar)); return false; } public static void main(String[] args) { TreeNode node1 = new TreeNode(1); TreeNode node2 = new TreeNode(2); TreeNode node3 = new TreeNode(3); TreeNode node4 = new TreeNode(4); TreeNode node5 = new TreeNode(5); TreeNode node6 = new TreeNode(6); TreeNode node7 = new TreeNode(7); node5.left = node3; node5.right = node6; node3.left = node1; node3.right = node4; node1.right = node2; FirstCommonAncestor fca = new FirstCommonAncestor(); fca.fircomanc(node5, node2, node2); if(fca.res == null) System.out.println("No Common Ancestor"); else System.out.println(fca.res.val); }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。