怎么求python二叉树中两个节点的最低公共父节点

这篇文章给大家介绍怎么求python二叉树中两个节点的最低公共父节点，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。

必须通过遍历查找一个节点的祖先集合，然后比较两个节点的祖先集合就可以找到最低的那个。这里采用后序遍历，并传入一个栈记录该节点的祖先节点。在每次访问一个节点时，先把这个节点压入栈，然后判断该节点是不是要查找的那个节点，如果是返回。接着查找它的左子树和右子树，当要查找的节点在它的左右子树中则返回。然后判断该节点与栈顶节点是否相同，是则弹出栈顶元素。这是因为相同就代表了在访问它的左右子树时没有添加新的节点，也就是说要查找的那个节点不在它的左右子树中，则该节点也就是不是要查找的节点的祖先。

#include#includeusing 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& 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 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 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二叉树中两个节点的最低公共父节点就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。