怎么求python二叉樹中兩個節點的最低公共父節點

這篇文章給大家介紹怎么求python二叉樹中兩個節點的最低公共父節點，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

必須通過遍歷查找一個節點的祖先集合，然后比較兩個節點的祖先集合就可以找到最低的那個。這里采用后序遍歷，并傳入一個棧記錄該節點的祖先節點。在每次訪問一個節點時，先把這個節點壓入棧，然后判斷該節點是不是要查找的那個節點，如果是返回。接著查找它的左子樹和右子樹，當要查找的節點在它的左右子樹中則返回。然后判斷該節點與棧頂節點是否相同，是則彈出棧頂元素。這是因為相同就代表了在訪問它的左右子樹時沒有添加新的節點，也就是說要查找的那個節點不在它的左右子樹中，則該節點也就是不是要查找的節點的祖先。

#include<iostream>
#include<stack>
using namespace std;
struct BinaryTreeNode
{
	int _data;
	BinaryTreeNode* _left;
	BinaryTreeNode* _right;
	BinaryTreeNode(int x)
		:_data(x)
		, _left(NULL)
		, _right(NULL)
	{}

};
class BinaryTree
{
private:
	BinaryTreeNode* _root;
private:
	void _Clear(BinaryTreeNode* root)
	{
		if (root == NULL)
			return;
		_Clear(root->_left);
		_Clear(root->_right);
		delete root;
	}
	BinaryTreeNode* _CreateBinary(int* arr, int& index, const int size)
	{
		BinaryTreeNode* ret = NULL;
		if (index < size&&arr[index] != '#')
		{
			ret = new BinaryTreeNode(arr[index]);
			ret->_left = _CreateBinary(arr, ++index, size);
			ret->_right = _CreateBinary(arr, ++index, size);
		}
		return ret;
	}
	BinaryTreeNode* _Find(BinaryTreeNode* root, int x)
	{
		if (root == NULL)
			return NULL;
		if (root->_data == x)
			return root;
		BinaryTreeNode* leftRet = _Find(root->_left, x);
		if (leftRet)
			return leftRet;
		BinaryTreeNode* rightRet = _Find(root->_right, x);
		return rightRet;
	}
	BinaryTreeNode* _GetPath(BinaryTreeNode* root, const BinaryTreeNode* child1, const BinaryTreeNode* child2)
	{
		if (root == NULL)
			return NULL;
		bool temp = isInclude(root, child1, child2);
		if (temp == false)
			return NULL;
		else
		{

			BinaryTreeNode* leftFind = _GetPath(root->_left, child1, child2);
			BinaryTreeNode* rightFind = _GetPath(root->_right, child1, child2);
			if (leftFind == NULL&&rightFind == NULL)
				return root;
			else if (leftFind == NULL&&rightFind)
				return rightFind;
			else
				return leftFind;
		}
	}
	bool isInclude(BinaryTreeNode* root, const BinaryTreeNode* child1, const BinaryTreeNode* child2)
	{
		if (root == NULL)
			return false;
		bool c1 = false, c2 = false;
		if (root == child1)
			c1 = true;
		if (root == child2)
			c2 = true;
		if (c1&&c2)
			return true;
		else
		{
			if (isInclude(root->_left, child1, child2))
				return true;
			else if (isInclude(root->_right, child1, child2))
				return true;
			else
				return false;
		}

	}
	bool _GetPathStack(BinaryTreeNode* root, BinaryTreeNode* child, stack<BinaryTreeNode*>& s)
	{
		if (root == NULL)
			return false;

		s.push(root);
		if (root == child)
		{
			return true;
		}
		if (_GetPathStack(root->_left, child, s))
			return true;

		if (_GetPathStack(root->_right, child, s))
		{
			return true;
		}

		s.pop();
		return false;
	}
public:
	BinaryTree()
		:_root(NULL)
	{}
	BinaryTree(int* arr, int size)
		:_root(NULL)
	{
		int index = 0;
		_root = _CreateBinary(arr, index, size);
	}
	~BinaryTree()
	{
		if (_root == NULL)
			return;
		_Clear(_root);
	}
	void PostOrder_NonR()
	{
		if (_root == NULL)
			return;
		stack<BinaryTreeNode*> s;
		BinaryTreeNode* cur = _root;
		BinaryTreeNode* prev = NULL;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}
			BinaryTreeNode* top = s.top();
			if (top->_right == NULL || prev&&prev == top->_right)
			{
				cout << top->_data << " ";
				prev = top;
				s.pop();
			}
			else
			{
				cur = top->_right;
			}
		}
		cout << endl;
	}
	BinaryTreeNode* Find(int x)
	{
		return _Find(_root, x);
	}
	BinaryTreeNode* LastCommonFather(BinaryTreeNode* child1, BinaryTreeNode* child2)
	{
		if (_root == NULL || child1 == NULL || child2 == NULL)
			return NULL;
		stack<BinaryTreeNode*> s1, s2;
		_GetPathStack(_root, child1, s1);
		_GetPathStack(_root, child2, s2);
		int size1 = s1.size();
		int size2 = s2.size();
		if (size1>size2)
		{
			int dif = size1 - size2;
			while (dif--)
			{
				s1.pop();
			}
		}
		else
		{
			int dif = size2 - size1;
			while (dif--)
			{
				s2.pop();
			}
		}
		BinaryTreeNode* top1 = NULL;
		BinaryTreeNode* top2 = NULL;
		if (!s1.empty() && !s2.empty())
		{
			top1 = s1.top();
			top2 = s2.top();
		}

		while (!s1.empty() && top1 != top2)
		{
			s1.pop();
			top1 = s1.top();
			s2.pop();
			top2 = s2.top();
		}
		return top1 == top2 ? top1 : NULL;
	}
	/*BinaryTreeNode* LastCommonFather(BinaryTreeNode* child1, BinaryTreeNode* child2)
	{
	if (_root == NULL || child1 == NULL || child2 == NULL)
	return NULL;
	return _GetPath(_root, child1, child2);
	}*/
};
int main()
{
	int arr[] = { 1, 2, 4, 8, '#', '#', '#', 5, '#', 9, '#', '#', 3, 6, '#', '#', 7 };
	BinaryTree bt(arr, sizeof(arr) / sizeof(arr[0]));
	bt.PostOrder_NonR();
	/*cout << bt.Find(9)->_data << endl;
	if (bt.Find(0))
	cout << bt.Find(0)->_data << endl;*/
	if (bt.LastCommonFather(bt.Find(9), bt.Find(7)))
		cout << bt.LastCommonFather(bt.Find(9), bt.Find(7))->_data << endl;
	system("pause");
}

關于怎么求python二叉樹中兩個節點的最低公共父節點就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。