2017百度面试现场coding算法三_算法面试coding题

三、求有孩子和兄弟指针树的最小公共子节点

struct TreeNode
{
    int value;
    TreeNode* first_child;
    TreeNode* next_sibling;
    TreeNode(int a):value(a),first_child(NULL),next_sibling(NULL){}
};
bool hasNode(TreeNode* pNode,TreeNode* p)
//判断以pNode为根的树中有没有节点
{
    bool flag1=false,flag2=false;
    if(pNode==NULL) return false;
    if(pNode==p)return true;//当前节点即是访问节点
  else
  {
   if(pNode->first_child!=NULL)
   {flag1=hasNode(pNode->first_child, p);//节点在孩子节点
    TreeNode* p1=pNode->first_child;
    while(p1->next_sibling!=NULL)//在同层兄弟节点中？
     {
       if(hasNode(p1->next_sibling, p))//找到
      {   flag2=true;
          break;
      }
       p1=p1->next_sibling;//循环查找是否在同层的其他节点
    }
   }
  }
    return flag1||flag2;//只要包含在孩子或者孩子的兄弟节点中
}
TreeNode* pubParent(TreeNode* root,TreeNode* p,TreeNode* q)
{
    TreeNode* pNode=root;
    while(hasNode(pNode, p)&&hasNode(pNode, q))//当前节点包含两个节点
    {
       bool flag1=false,flag2=false;
       if(pNode->first_child!=NULL&&hasNode(pNode->first_child, p)&&hasNode(pNode->first_child, q))
       //判断是否在孩子节点所在的树中
        {    pNode=pNode->first_child,flag1=true;}
        else if(pNode->first_child->next_sibling!=NULL)//判断是否在孩子同层的某个兄弟树中
        {
            TreeNode* p1=pNode->first_child;
            while(p1->next_sibling!=NULL)
            {
              if(hasNode(p1->next_sibling, p)&&hasNode(p->next_sibling, q))//找到包含的兄弟树
                {    pNode=p1->next_sibling;
                     //继续以兄弟树为根查找
                     flag2=true;
                     break;
                }
                else
                     p1=p1->next_sibling;
            }
            if(flag2==true)//当包含在其中之一的兄弟节点，则以该节点为根，继续查找
                break;
        }
        if(flag1==false&&flag2==false)//若没有在孩子节点和孩子的兄弟节点中，则只在当前节点中，返回当前节点
            return pNode;
    }
    return pNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61