首页 > 代码库 > 二棵树某两个节点的公共祖先。

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

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

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

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

  2.  CC150,递归求解。

 

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

}