두 노드 의 가장 가 까 운 공공 조상 을 찾다.

일반 이 진 트 리 중 두 노드 가 가장 가 까 운 공공 조상 을 찾 아 보 세 요.방법: 1. 두 노드 가 뿌리 노드 에서 떨 어 지 는 경 로 를 찾 아 스 택 에 저장 합 니 다.2. 두 스 택 의 길이 가 같 는 지 판단 하고 같 지 않 으 면 pop () 에서 size () 값 이 큰 하 나 를 떨 어 뜨 려 두 스 택 의 길이 가 같 을 때 까지 합 니 다.3. 각각 두 개의 스 택 지붕 의 요 소 를 취하 고 비교 값 이 같 는 지, 같 지 않 으 면 두 개의 스 택 지붕 요 소 를 모두 스 택 에서 나 오고 같 으 면 스 택 꼭대기 요 소 를 되 돌려 줍 니 다.

using namespace std;
template <class T>
struct BinaryTreeNode//        
{
    BinaryTreeNode(const T& value)
        :_value(value)
        ,_pLeft(NULL)
        ,_pRight(NULL)
    {}
    T _value;
    BinaryTreeNode* _pLeft;
    BinaryTreeNode* _pRight;
};
template<class T>
class BinaryTree//     
{
    typedef BinaryTreeNode Node;
public:
    BinaryTree()
        :_pRoot(NULL)
    {}
private:
    Node* _pRoot;//   
};

이 진 트 리 의 가장 가 까 운 공공 조상 찾기:

Node* FindCommonAncestorNode(Node* first, Node* second)
    {
        if(!_pRoot || !first || !second)
            return NULL;
        return _FindCommonAncestorNode(_pRoot, first, second);
    }
    void Stack(stack& s, Node* _pRoot, Node* first)//             
    {
        Node* pCur = _pRoot;
        Node* pPre = NULL;
        while(pCur || !s.empty())
        {
            while(pCur)
            {
                s.push(pCur);
                pCur = pCur->_pLeft;
            }
            Node* pTop = s.top();
            if(pTop->_pRight == NULL || pTop->_pRight == pPre)
            {
                if(pTop->_value == first->_value)
                    break;
                s.pop();
                pPre = pTop;
            }
            else
                pCur = pTop->_pRight;
        }
    }
    Node* _FindCommonAncestorNode(Node* _pRoot, Node* first, Node* second)
    {
        stack s1;
        stack s2;
        Stack(s1, _pRoot, first);
        Stack(s2, _pRoot, second);
        while(s1.size() > s2.size())
        {
            s1.pop();
        }
        while(s1.size() < s2.size())
        {
            s2.pop();
        }
        while(s1.top() != s2.top())
        {
            s1.pop();
            s2.pop();
        }
        return s1.top();
    }