Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1003462
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: C/C++

2012-10-23 15:40:48

75.二叉树两个结点的最低共同父结点
题目:二叉树的结点定义如下:
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点。

解释:
给定一个根节点node,和两个节点a, b.getLCA查询a,或b是否是head的孩子。
Node *getLCA(Node* head, Node* a, Node* b)

1.对于一个节点node,
当node == a 或 node == b:
说明在当前节点中发现了a或b,返回当前节点。

2.否则,分别在node的左右子树中查询a,b
Node *tl = getLCA(head->left, a, b);
Node *tr = getLCA(head->right, a, b);
3.如果node的左节点是a,b的公共父节点,则在其右子树中尝试查询a,b最后结果必然是NULL
反之亦然。
所以当node的左右节点查询结果都不为空的时候,说明该点就是最近公共父节点。

4.当左右子树的查询结果只有一个是空的话,返回不为空的那个。有两种可能性
tl(tl!= NULL) 或tr (tr!=NULL),直到返回3的时候终结。



点击(此处)折叠或打开

  1. Node *getLCA(Node* head, Node* a, Node* b){
  2.     if(head == NULL) return NULL;
  3.     if(a == head || b == head){
  4.                return head;
  5.         }
  6.     Node *tl = getLCA(head->left, a, b);
  7.     Node *tr = getLCA(head->right, a, b);
  8.     if(tl!=NULL && tr!=NULL){
  9.         return (tl!=tr ? head : tl);
  10.     }
  11.     if(tl != NULL) return tl;
  12.         if(tr != NULL) return tr;
  13.         return NULL;
  14. }

阅读(3939) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~