Cracking the coding interview--Q4.6 - - 博客频道 - CSDN.NET
Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
译文:
设计算法并写代码在一个二叉树中找出两个结点的第一个共同祖先。避免存储额外的结点。注意:这里不特指二叉查找树。
解答
若使用额外的存储空间,最简单的方式就是对于一个结点向父节点进行遍历,直至根结点。可以考虑存储为hash,然后对另一个结点向父节点进行遍历,同时和第一个结点的父节点,所组成的hash集合进行比较,第一个相同的结点即为二者的共同祖先;
若不能使用额外的存储空间,则只能是不断的取一个节点的父节点,然后同另外一个节点的所有父节点进行比较,直到根节点;
另外如果节点没有父指针,那么则需要从根节点开始遍历,依次判断每个节点,是否可以到达问题中的两个节点。找到最后一个这样的节点即可
如果数据结构Node中不允许有指向父亲结点的指针, 那么我们又该如何处理?其实也很简单,首先根结点一定为任意两个结点的共同祖先, 从根结点不断往下找,直到找到最后一个这两结点的共同祖先.
Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
译文:
设计算法并写代码在一个二叉树中找出两个结点的第一个共同祖先。避免存储额外的结点。注意:这里不特指二叉查找树。
解答
若使用额外的存储空间,最简单的方式就是对于一个结点向父节点进行遍历,直至根结点。可以考虑存储为hash,然后对另一个结点向父节点进行遍历,同时和第一个结点的父节点,所组成的hash集合进行比较,第一个相同的结点即为二者的共同祖先;
若不能使用额外的存储空间,则只能是不断的取一个节点的父节点,然后同另外一个节点的所有父节点进行比较,直到根节点;
另外如果节点没有父指针,那么则需要从根节点开始遍历,依次判断每个节点,是否可以到达问题中的两个节点。找到最后一个这样的节点即可
public static TreeNode ancestor; //使用额外的空间存储 public static TreeNode method1(TreeNode tn1,TreeNode tn2){ if(tn1==null||tn2==null) return null; HashSet<TreeNode> set=new HashSet<TreeNode>(); while(tn1.parent!=null){ set.add(tn1); tn1=tn1.parent; } while(tn2.parent!=null){ if(set.contains(tn2)) return tn2; tn2=tn2.parent; } return null; } //不使用额外的空间 public static TreeNode method2(TreeNode tn1,TreeNode tn2){ if(tn1==null||tn2==null) return null; for(TreeNode p=tn1;p!=null;p=p.parent){ TreeNode q=tn2; while(q.parent!=null){ if(q==p) return q; q=q.parent; } } return null; } //不存在父指针的节点 //ancestor会不断更新,直到最后一个共同的祖先 public static void method3(TreeNode tn1,TreeNode tn2,TreeNode head){ if(head==null||tn1==null||tn2==null) return; if(head!=null&&father(head,tn1)&&father(head,tn2)){ ancestor=head; method3(tn1,tn2,head.lchild); method3(tn1,tn2,head.rchild); } } private static boolean father(TreeNode head,TreeNode tnode){ if(head==null) return false; else if(head==tnode) return true; else return father(head.rchild,tnode)||father(head.lchild,tnode); }http://www.hawstein.com/posts/4.6.html
如果数据结构Node中不允许有指向父亲结点的指针, 那么我们又该如何处理?其实也很简单,首先根结点一定为任意两个结点的共同祖先, 从根结点不断往下找,直到找到最后一个这两结点的共同祖先.
void first_ancestor2(Node* head, Node* n1, Node* n2, Node* &ans){
if(head==NULL || n1==NULL || n2==NULL) return;
if(head && father(head, n1) && father(head, n2)){
ans = head;
first_ancestor2(head->lchild, n1, n2, ans);
first_ancestor2(head->rchild, n1, n2, ans);
}
}
Read full article from Cracking the coding interview--Q4.6 - - 博客频道 - CSDN.NET