关于二叉树的面试题

1.前序/中序/后序遍历/层序遍历

   见我的博客：二叉树的遍历（递归）、二叉树的遍历（非递归）

2.求二叉树的高度
 
   见我的博客：二叉树的实现

3.求叶子节点的个数
 
 

int _GetLeafNum(BinaryTreeNode<T>*root)
    {
        static int count = 0;
        if(root == NULL)
        {
            return 0;
        }
        else if(root->_left == NULL&&root->_right ==NULL)
        {
            count++;
        }
        _GetLeafNum(root->_left);
        _GetLeafNum(root->_right);
        return count;
    }

  其他思路：一个二叉树中叶子节点的个数时度为2的节点的个数减1，所以只要计算出度为二的结点有多少再减1即可（即判断一个结点的左右孩子是否为空，都不为空则+1）。

4.判断一个结点是否在二叉树中

bool _Find(BinaryTreeNode<T> *root,const T& x)
{
    if(root == NULL)
    {
        return NULL;
    }
    else if(root->_data == x)
    {
        return true;
    }
    else
    {
        if(root->_left)
        {
            BinaryTreeNode<T> *tmp = _Find(root->_left,x);
            if(tmp)
                return tmp;
            else if(root->_right)
            {
                return _Find(root->_right,x);
            }
        }
    }
    return false;
}

5.求二叉树第k层的节点个数

int _GetLevelLeafNum(const BinaryTreeNode<T> * root,const int k)
    {
        static int count = 0;
        if(root == NULL||k < 0)
        {
            return 0;
        }
        if(k == 0)
        {
            count++;
        }
        _GetLevelLeafNum(root->_left,k-1);
        _GetLevelLeafNum(root->_right,k-1);
        return count;
    }

6.求两个节点的最近公共祖先    LCA问题

（1）当树为查找树时
     思路：假设当前结点为cur,两个节点分别为left,right(保证right>left,如果不是就交换)。
               当cur小于ight，left时，去cur的左子树找              
               当cur大于right,left时，去cur的右子树找
               当cur在right，left中间时，即为cur              
                当right为left的父节点，为right,反过来则为left

int FindLowestCommonAncestor(BinaryTreeNode<T> *cur, BinaryTreeNode<T> *u,BinaryTreeNode<T> *v)
{
    int left = u._data;
    int right = v._data;
    BinaryTreeNode<T> parent = NULL;

    //保证left < right
    if (left > right)
    {
        swap(right,left);
    }

    while (true)
    {
        if (cur->_data < left)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_data > right)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_data == left || cur->_data == right)
        {
            return parent._data;
        }
        else
        {
            return cur->_data;
        }
    }
}

 (2)当树为普通树时
       1.有父指针时
      思路：当有父指针时，利用指针的回溯，可以得到单链表，那么问题就转换成了求两条链表相交的第一个节点。这个问题以前在我的博文《关于单链表的面试题》里分析过，请回戳^_^
      另：可以用栈来保存两个链表。
       2.没有父指针时
      

BinaryTreeNode<T>* FindLowestCommonAncestor(BinaryTreeNode<T> *u,BinaryTreeNode<T> *v)
    {
        //flag为0两个节点都没找到，为1找了一个结点，2则找祖先成功。
        int flag = 0;
        BinaryTreeNode<T> *tmp = _FindAncestor(_root,u,v,flag);
        if(flag == 2)
        {
            return tmp;
        }
        return NULL;
    }
private:
    BinaryTreeNode<T>* _FindAncestor(BinaryTreeNode<T>* root,BinaryTreeNode<T>* u,BinaryTreeNode<T>* v,int &flag)
    {
        if(root == NULL || flag == 2)
        {
            return NULL;
        }
        BinaryTreeNode<T> *tmp = NULL;

        if(root == u||root == v)
        {
            ++flag;
            if(flag == 2)
            {
                return root;
            }
            else
            {
                tmp = root;
            }
        }
        BinaryTreeNode<T>* left = _FindAncestor(root->_left,u,v,flag);
        BinaryTreeNode<T>* right = _FindAncestor(root->_right,u,v,flag);

        if(left && right)
        {
            return root;
        }
        else if(left || right)
        {
            tmp = left?left:right;
            if(flag == 2)
            {
                if(tmp == u||tmp == v)
                {
                    return tmp;
                }
            }
        }
        return tmp;
    }

7.判断一棵二叉树是否是平衡二叉树
    

bool _IsBalance(Node* root)
    {
        if(root == NULL)
        {
            return true;
        }
        int left = _Height(root->_left);
        int right = _Height(root->_right);

        int bf = left - right;
        if(abs(bf) > 1)
        {
            return false;
        }
        if(abs(bf) != abs(root->_bf))
        {
            return false;
        }
        return _IsBalance(root->_left)&&_IsBalance(root->_right);
    }

8.求二叉树中最远的两个节点的距离(二叉树中相距最远的两个节点之间的距离)

void NodeMaxDistance()
    {
        int max = 0;
        _NodeMaxDistance(_root,max);
        cout<<"Distance:"<<max<<endl;
    }
private:
    int _NodeMaxDistance(BinaryTreeNode<T> *root,int &max)
    {
        if(root == NULL)
        {
            return -1;
        }
        int lDistance = 1 + _NodeMaxDistance(root->_left,max);
        int rDistance = 1 + _NodeMaxDistance(root->_right,max);

        if (lDistance + rDistance > max)
        {
            max = lDistance + rDistance;
        }
        return  lDistance > rDistance ? lDistance : rDistance;
    }

9.由前序遍历，中序遍历重建二叉树

void ReBuildBinaryTree(int* pPreOrder, int* pInOrder,int nodeNum)
    {
        _root = _ReBuildBinaryTree(pPreOrder,pInOrder,nodeNum);
    }

private:
    BinaryTreeNode<T>* _ReBuildBinaryTree(int* pPreOrder, int* pInOrder, int nodeNum)
    {
        if(pPreOrder == NULL || pInOrder == NULL || nodeNum <= 0)
        {
            return NULL;
        }
        BinaryTreeNode<T> *newRoot = new BinaryTreeNode<T>;
        // 前序遍历的第一个为根
        newRoot ->_data = pPreOrder[0];
        newRoot ->_left = NULL;
        newRoot ->_right = NULL;

        // 查找根节点在中序遍历中的位置，中序遍历中，根节点左边为左子树，右边为右子树
        int rootPositionInOrder;
        for(int i = 0; i < nodeNum; i++)
        {
            if(pInOrder[i] == newRoot->_data)
            {
                rootPositionInOrder = i;
                break;
            }
        }

        // 重建左子树
        int nodeNumLeft = rootPositionInOrder;
        int * pPreOrderLeft = pPreOrder + 1;
        int * pInOrderLeft = pInOrder;
        newRoot->_left = _ReBuildBinaryTree(pPreOrderLeft, pInOrderLeft, nodeNumLeft);

        // 重建右子树
        int nodeNumRight = nodeNum - nodeNumLeft - 1;
        int * pPreOrderRight = pPreOrder + 1 + nodeNumLeft;
        int * pInOrderRight = pInOrder + nodeNumLeft + 1;
        newRoot->_right = _ReBuildBinaryTree(pPreOrderRight, pInOrderRight, nodeNumRight);
        return newRoot;
    }

10.判断一棵树是否为完全二叉树
思路：层序遍历二叉树，当一个结点的左子树为空时，右子树必须存在，且后面遍历到的结点左右子树都为空。符合此条件的树即为完全二叉树。

bool IsCompleteBinaryTree()
    {
        return _IsCompleteBinaryTree(_root);
    }
private:
    bool _IsCompleteBinaryTree(BinaryTreeNode<T>* root)
    {
        if(root == NULL)
        {
            return false;
        }
        queue<BinaryTreeNode<T>*> q;
        q.push(root);
        bool MustHaveNoChild = false;

        while(!q.empty())
        {
            BinaryTreeNode<T>* cur = q.front();
            q.pop();
            if(MustHaveNoChild)
            {
                if(cur->_left != NULL || cur->_right != NULL)
                {
                    return false;
                }
            }
            else
            {
                if(cur->_right && cur->_left)
                {
                    q.push(cur->_left);
                    q.push(cur->_right);
                }
                else if(cur->_left && cur->_right == NULL)
                {
                    MustHaveNoChild = true;
                    q.push(cur->_left);
                }
                else if(cur->_right && cur->_left == NULL)
                {
                    return false;
                }
                else
                {
                    //两边都没有
                    MustHaveNoChild = true;
                }
            }
        }
        return true;
    }

11.求二叉树镜像

BinaryTreeNode<T>* _Mirror(BinaryTreeNode<T> *& root)
    {
        if(root == NULL)
        {
            return NULL;
        }
        BinaryTreeNode<T> *pLeft = _Mirror(root->_left);
        BinaryTreeNode<T> *pRight = _Mirror(root->_right);

        root->_left = pRight;
        root->_right = pLeft;
        return root;
    }

12.将二叉搜索树转化为一个排序的双向链表，要求不能创建任何新的结点，只能调整树结点中指针的指向。
思路：
  分为以下两种情况：

void TransToList()
    {
        BinaryTreeNode<T>* FirstNode = NULL;
        BinaryTreeNode<T>* LastNode = NULL;
        _TranToList(_root,FirstNode,LastNode);
    }
private:
    void _TranToList(BinaryTreeNode<T>* root,BinaryTreeNode<T>*& first,BinaryTreeNode<T>*& last)
    {
        if(root == NULL)
        {
            first = NULL;
            last = NULL;
            return;
        }

        BinaryTreeNode<T>* firstLeft = NULL,*lastLeft = NULL,*firstRight = NULL,*lastRight = NULL;
        //论左
        if(root->_left == NULL)
        {
            first = root;
        }
        else
        {
            _TranToList(root->_left,firstLeft,lastLeft);
            first = firstLeft;

              //连指针

            root->_left = lastLeft;
            if(lastLeft)
            {
                lastLeft->_right = root;
            }
        }
        //论右
        if(root->_right == NULL)
        {
            last = root;
        }
        else
        {
            _TranToList(root->_right,firstRight,lastRight);
            last = lastRight;

            //连指针
            root->_right = firstRight;
            if(firstRight)
            {
                firstRight->_left = root;
            }
        }
        return;
    }