C++算法之求二叉树两个节点的最低公共节点

方法1：递归方法：

（1）如果两个节点分别在根节点的左子树和右子树，则返回根节点
（2）如果两个节点都在左子树，则递归处理左子树；如果两个节点都在右子树，则递归处理右子树

bool FindNode(BTree* pRoot, BTree* pNode)
{
 if (pRoot == NULL || pNode == NULL)
 {
  return false;
 }
 if (pRoot == pNode)
 {
  return true;
 }

 bool found = FindNode(pRoot->m_nLeft, pNode);
 if (!found)
 {
  found = FindNode(pRoot->m_nRight,pNode);
 }

 return found;
}

BTree* GetCommentParent(BTree* pRoot, BTree* pNode1, BTree* pNode2)
{
 if (FindNode(pRoot->m_nLeft,pNode1))
 {
  if (FindNode(pRoot->m_nRight, pNode2))
  {
   return pRoot;//如果两个节点分别在根节点的左子树和右子树，则返回根节点
  }
  else//如果两个节点都在左子树，则递归处理左子树
  {
   return GetCommentParent(pRoot->m_nLeft,pNode1,pNode2);
  }
 }
 else
 {
  if (FindNode(pRoot->m_nLeft,pNode2))
  {
   return pRoot;//如果两个节点分别在根节点的左子树和右子树，则返回根节点
  }
  else//如果两个节点都在右子树，则递归处理右子树
  {
   return GetCommentParent(pRoot->m_nRight,pNode1,pNode2);
  }
 }
}

方法2：

非递归解法：
先求从根节点到两个节点的路径，然后再比较对应路径的节点就行，最后一个相同的节点也就是他们在二叉树中的最低公共祖先节点

bool GetNodePath(BTree* pRoot, BTree* pNode, list<BTree*> & path)
{
 if (pRoot == pNode)
 {
  path.push_back(pRoot);
  return true;
 }
 if (pRoot == NULL)
 {
  return false; 
 }

 path.push_back(pRoot);
 bool found = false;
 found = GetNodePath(pRoot->m_nLeft,pNode,path);
 if (!found)
 {
  found = GetNodePath(pRoot->m_nRight,pNode,path);
 }
 if (!found)
 {
  path.pop_back();
 }
 return found;
}

BTree* GetCommentParent2(BTree* pRoot,BTree* pNode1,BTree* pNode2)
{
 if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
 {
  return NULL;
 }
 list<BTree*> path1;
 list<BTree*> path2;
 bool bResult1 = GetNodePath(pRoot,pNode1,path1);
 bool bResult2 = GetNodePath(pRoot,pNode2,path2);
 if (!bResult1 || !bResult2)
 {
  return NULL;
 }

 list<BTree*>::const_iterator iter1 = path1.begin();
 list<BTree*>::const_iterator iter2 = path2.begin();
 BTree* pCommentParent = NULL;
 while (iter1 != path1.end() && iter2 != path2.end())
 {
  if (*iter1 == *iter2)
  {
   pCommentParent = *iter1;
  }
  
  iter1++;
  iter2++;
 }

 return pCommentParent;
}

完整测试代码：

// FindCommentParent.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <list>
#include <queue>
using namespace std;

//节点的数据结构
class BTree
{
public:
 int       m_nValue;
 BTree*    m_nLeft;
 BTree*    m_nRight;
public:
 BTree(int value)
 {
  m_nValue = value;
 }
};

//二叉树的插入实现
void Insert(int value, BTree* &root)
{
 if (root == NULL)
 {
  root = new BTree(value);
 }
 else if(value < root->m_nValue)
  Insert(value,root->m_nLeft);
 else if(value > root->m_nValue)
  Insert(value,root->m_nRight);
 else
  ;
}

bool FindNode(BTree* pRoot, BTree* pNode)
{
 if (pRoot == NULL || pNode == NULL)
 {
  return false;
 }
 if (pRoot == pNode)
 {
  return true;
 }

 bool found = FindNode(pRoot->m_nLeft, pNode);
 if (!found)
 {
  found = FindNode(pRoot->m_nRight,pNode);
 }

 return found;
}

BTree* GetCommentParent(BTree* pRoot, BTree* pNode1, BTree* pNode2)
{
 if (FindNode(pRoot->m_nLeft,pNode1))
 {
  if (FindNode(pRoot->m_nRight, pNode2))
  {
   return pRoot;//如果两个节点分别在根节点的左子树和右子树，则返回根节点
  }
  else//如果两个节点都在左子树，则递归处理左子树
  {
   return GetCommentParent(pRoot->m_nLeft,pNode1,pNode2);
  }
 }
 else
 {
  if (FindNode(pRoot->m_nLeft,pNode2))
  {
   return pRoot;//如果两个节点分别在根节点的左子树和右子树，则返回根节点
  }
  else//如果两个节点都在右子树，则递归处理右子树
  {
   return GetCommentParent(pRoot->m_nRight,pNode1,pNode2);
  }
 }
}

bool GetNodePath(BTree* pRoot, BTree* pNode, list<BTree*> & path)
{
 if (pRoot == pNode)
 {
  path.push_back(pRoot);
  return true;
 }
 if (pRoot == NULL)
 {
  return false; 
 }

 path.push_back(pRoot);
 bool found = false;
 found = GetNodePath(pRoot->m_nLeft,pNode,path);
 if (!found)
 {
  found = GetNodePath(pRoot->m_nRight,pNode,path);
 }
 if (!found)
 {
  path.pop_back();
 }
 return found;
}

BTree* GetCommentParent2(BTree* pRoot,BTree* pNode1,BTree* pNode2)
{
 if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
 {
  return NULL;
 }
 list<BTree*> path1;
 list<BTree*> path2;
 bool bResult1 = GetNodePath(pRoot,pNode1,path1);
 bool bResult2 = GetNodePath(pRoot,pNode2,path2);
 if (!bResult1 || !bResult2)
 {
  return NULL;
 }

 list<BTree*>::const_iterator iter1 = path1.begin();
 list<BTree*>::const_iterator iter2 = path2.begin();
 BTree* pCommentParent = NULL;
 while (iter1 != path1.end() && iter2 != path2.end())
 {
  if (*iter1 == *iter2)
  {
   pCommentParent = *iter1;
  }
  
  iter1++;
  iter2++;
 }

 return pCommentParent;
}

BTree*  findOneNode(BTree* pRoot, int value)
{
 if (pRoot == NULL)
 {
  return NULL;
 }
 queue<BTree*> q;
 q.push(pRoot);
 BTree* ret = NULL;
 while (!q.empty())
 {
  BTree* pNode = q.front();
  q.pop();
  if (pNode->m_nValue == value)
  {
   return pNode;
  }
  else
  {
   if (pNode->m_nLeft != NULL)
   {
    q.push(pNode->m_nLeft);
   }
   if (pNode->m_nRight != NULL)
   {
    q.push(pNode->m_nRight);
   }
  }
 }
}

int _tmain(int argc, _TCHAR* argv[])
{
 BTree* m_pRoot = new BTree(5);
 Insert(6,m_pRoot);
 Insert(3,m_pRoot);
 Insert(4,m_pRoot);
 Insert(2,m_pRoot);

 BTree* node = findOneNode(m_pRoot,2);
 BTree* node2 = findOneNode(m_pRoot,6);

 BTree* pNode = GetCommentParent2(m_pRoot,node,node2);
 cout<<pNode->m_nValue<<endl;
 getchar();
 return 0;
}

C++算法之 求二叉树两个节点的最低公共节点

C++算法之求二叉树两个节点的最低公共节点