二棵树某两个节点的公共祖先。

时间:2014-08-21 01:29:33   收藏:0   阅读:348

1. 如果是有parent指针的树,可以转化成 求两个链表第一个公共节点的问题。

对于无parent指针普通二叉树(假定这两个节点一定在树中,否则需要先遍历一边树查找是否存在该节点)

  1. (剑指offer的解法),先用一定的空间记录从根节点到两个节点各自的路径,然后找这两个路径最后一个相交的节点。

  2.  CC150,递归求解。

 

TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){

}

 

二棵树某两个节点的公共祖先。,布布扣,bubuko.com

原文:http://www.cnblogs.com/jdflyfly/p/3926034.html

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!