二叉樹の面接試験問題

1.前の順序/中の順序/後の順序(再帰ではない)前の順序を巡回します.

void PrevOrderNonR()
    {
        stack s;
        Node* cur = _root;

        while (cur || !s.empty())
        {
            while (cur)
            {
                cout<_data<<" ";
                s.push(cur);
                cur = cur->_left;
            }

            // top                   
            //          ，         
            Node* top = s.top();
            s.pop();

            //           
            cur = top->_right;
        }

        cout<

中順

void InOrder()
    {
        _InOrder(_root);
        cout<void InOrderNonR()
    {
        Node* cur = _root;
        stack s;
        while (cur || !s.empty())
        {
            while (cur)
            {
                s.push(cur);
                cur = cur->_left;
            }

            Node* top = s.top();
            s.pop();

            cout<_data<<" ";

            //    
            cur = top->_right;
        }
    }

後序

 void PostOrderNonR()
    {
        Node* cur = _root;
        stack s;
        Node* prev = NULL;

        while (cur || !s.empty())
        {
            while (cur)
            {
                s.push(cur);
                cur = cur->_left;
            }

            Node* front = s.top();
            if (front->_right == NULL || front->_right == prev)
            {
                cout<_data<<" ";
                prev = front;
                s.pop();
            }
            else
            {
                //    
                cur = front->_right;
            }
        }
        cout<

一本の二叉の木がバランス二叉の木かどうかを判断します.

//             
bool IsBalancedTree_old(Node* root)
{
    if (root == NULL)
        return true;
    int lenleft = BinaryTreeDepth(root->Lchild);//     ，      ，     N^2
    int lenright = BinaryTreeDepth(root->Rchild);
    int temp = lenleft - lenright;
    if (temp >1 || temp < -1)
        return false;
    return IsBalancedTree_old(root->Lchild) && IsBalancedTree_old(root->Rchild);//    ，            
}




//          (  )
bool _IsBlancedtree_new(Node* root,int* pDepth)
{
    if (root == NULL)
    {
        *pDepth = 0;
        return true;
    }
    int left, right;
    if (_IsBlancedtree_new(root->Lchild, &left) && _IsBlancedtree_new(root->Rchild, &right))//      
    {
        int temp = left - right;
        if (temp <= 1 && temp >= -1)//     
        {
            *pDepth = left > right ? left + 1 : right + 1;
            return true;
        }
    }

    return false;
}
bool IsBlancedTree_new(Node* root)
{
    int pDepth;
    bool tag = _IsBlancedtree_new(root, &pDepth);
    return tag;
}

二叉の木の鏡像を求めます.

//          ：       
void  Mirror(Node* root)
{
    if (root == NULL)
        return ;
    if (root->Lchild == NULL && root->Rchild == NULL)
        return ;
    Node* temp = root->Lchild;//      
    root->Lchild = root->Rchild;
    root->Rchild = temp;
    if (root->Lchild)//    
        MirrorRecursively(root->Lchild);
    if (root->Rchild)
        MirrorRecursively(root->Rchild);
}

二つのノードの最近の共通の祖先を求めます.

bool GetNodePath(Node* root, Node* x, stack& paths)
    {
        if (root == NULL)
            return false;

        paths.push(root);
        if (root == x)
            return true;

        if(GetNodePath(root->_left, x, paths))
            return true;

        if (GetNodePath(root->_right, x, paths))
            return true;

        paths.pop();
        return false;
    }

Node* GetCommonAncestor(Node* root, Node* x1, Node* x2)
    {
        assert(x1 && x2);
        stack paths1;
        stack paths2;
        if (GetNodePath(root, x1, paths1) == false)
            return NULL;
        if (GetNodePath(root, x2, paths2) == false)
            return NULL;

        while(paths1.size() != paths2.size())
        {
            if (paths1.size() > paths2.size())
                paths1.pop();
            else
                paths2.pop();
        }

        while (1)
        {
            if (paths1.top() == paths2.top())
            {
                return paths1.top();
            }

            paths1.pop();
            paths2.pop();
        }

    }

Node * FindLCA(Node * node, Node * target1, Node * target2)
{
    if (node == nullptr)
        return nullptr;
    if (node == target1 || node == target2)
        return node;

    Node * left = FindLCA(node->left, target1, target2);
    Node * right = FindLCA(node->right, target1, target2);
    if (left && right)  //        
        return node;

    return left ? left : right;  //          
}

二叉の木の中で一番遠い二つのノードの距離を求めます.

int _FindMaxLen(Node* root, int& maxLen)
    {
        if (root == NULL)
            return 0;

        int l = _FindMaxLen(root->_left, maxLen);
        int r = _FindMaxLen(root->_right, maxLen);
        if (l+r > maxLen)
        {
            maxLen = l+r;
        }

        return l > r ? l+1 : r+1;
    }

    int FindMaxLen(Node* root)
    {
        int max = 0;
        _FindMaxLen(root, max);
        return max;
    }

    //void _FindMaxLen(Node* root, int& maxLen)
    //{
    //  if (root == NULL)
    //      return;
    //  
    //  int l = Height(root->_left);
    //  int r = Height(root->_right);
    //  if (l + r > manLen)
    //      manLen = l + r;

    //  FindMaxLen(root->_left);
    //  FindMaxLen(root->_right);
    //}

二叉樹は、前の順序で巡回して再構成されます.

Node* ReBulidTree(char*& prev, char* inStart, char* inEnd)
    {
        if (*prev=='\0')
            return NULL;

        Node* root = new Node(*prev);
        if (inStart == inEnd)
            return root;

        char* pos = inStart;
        while (pos <= inEnd)
        {
            if (*pos == *prev)
                break;
            ++pos;
        }
        assert(pos <= inEnd);

        // [inStart,pos-1]
        // [pos+1,inEnd]
        root->_left = ReBulidTree(++prev, inStart, pos-1);
        root->_right = ReBulidTree(++prev, pos+1, inEnd);

        return root;
    }

一本の木が完全に二叉の木かどうかを判断します.

bool IsCompleteTree(Node* root)
    {
        if (root == NULL)
            return true;

        bool tag = true;
        queue q;
        q.push(root);
        while (!q.empty())
        {
            Node* front = q.front();
            q.pop();
            if (front->_left)
            {
                if (tag == false)
                    return false;

                q.push(front->_left);
            }
            else
            {
                tag = false;
            }

            if (front->_right)
            {
                if (tag == false)
                    return false;

                q.push(front->_right);
            }
            else
            {
                tag = false;
            }
        }

        return true;
    }

二叉検索ツリーを並べ替えた双方向チェーンテーブルです.任意の新しい結点を作成することができず、ツリー内の結点ポインタの方向を調整するしかないことを要求します.

Node* ToSortList(Node* root)
    {
        Node* prev = NULL;
        ToSortList(root, prev);

        while (root && root->_left)
        {
            root = root->_left;
        }

        return root;
    }

    Node* _ToSortList(Node* cur, Node*& prev)
    {
        if (cur == NULL)
            return;

        _ToSortList(cur->_left, prev);

        cur->_left = prev;
        if (prev)
            prev->_right = cur;

        prev = cur;

        _ToSortList(cur->_right, prev);
    }
}