Work

关于树的几个题<各种转>

求BST中两个节点的公共父节点
BST 二叉搜索树 特点: 每个节点的左子树都小于它 右子树都大于它
思路:
   
基本思想是：给定二叉树中的两个节点n1, n2(假定n1<n2), 其最近的公共祖先节点的值n应该满足 n1<n<n2，所以我们可以前序遍历二叉搜索树，当发现一个节点的值在n1和n2之间时，则此节点为所求节点。如果节点的值大于n1和n2，则所求节点在当前节点的左子树；否则在右子树。（算法很简单，对于树的求解关键是用好先中后序遍历，再难也不过如此，呵呵）

posted on 2011-09-20 23:02 lonelycastle 阅读(59) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理