【摘要】计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。二叉树是递归定义的，因此，与二叉树有关的题目基本都可以用递归思想解决，当然有些题目非递归解法也应该掌握，如非递归遍历节点等等。本文努力对二叉树相关题目做一个较全的整理总结，希望对找工作的同学有所帮助。
本文内容如下所示 1. 求二叉树中的节点个数 2. 求二叉树的深度 3. 前序遍历，中序遍历，后序遍历 4. 分层遍历二叉树（按层次从上往下，从左往右） 5. 将二叉查找树变为有序的双向链表 6. 求二叉树第K层的节点个数 7. 求二叉树中叶子节点的个数 8. 判断两棵二叉树是否结构相同 9. 判断二叉树是不是平衡二叉树 10. 求二叉树的镜像 11. 求二叉树中两个节点的最低公共祖先节点 12. 求二叉树中节点的最大距离 13. 由前序遍历序列和中序遍历序列重建二叉树 14. 判断二叉树是不是完全二叉树
二叉树节点定义
struct BinaryTreeNode{int m_nValue;BinaryTreeNode* m_pLeft;BinaryTreeNode* m_pRight;};1、求二叉树中的节点个数
递归解法： （1）如果二叉树为空，节点个数为0 （2）如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1 参考代码如下：
int GetNodeNum(BinaryTreeNode * pRoot){;return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;}2、求二叉树的深度
递归解法： （1）如果二叉树为空，二叉树的深度为0 （2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1 参考代码如下：
int GetDepth(BinaryTreeNode * pRoot){;int depthLeft = GetDepth(pRoot->m_pLeft);int depthRight = GetDepth(pRoot->m_pRight);return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1); }3、前序遍历，中序遍历，后序遍历
前序遍历递归解法： （1）如果二叉树为空，空操作 （2）如果二叉树不为空，先访问根节点，然后遍历左子树，再遍历右子树 参考代码如下：
void PreOrderTraverse(BinaryTreeNode * pRoot){if(pRoot == NULL)return;printf(“%d\n”,pRoot->data); // 显示结点数据PreOrderTraverse(pRoot->m_pLeft); // 前序遍历左子树PreOrderTraverse(pRoot->m_pRight); // 前序遍历右子树}
中序遍历递归解法 （1）如果二叉树为空，空操作。 （2）如果二叉树不为空，先遍历左子树，然后访问根节点，再遍历右子树 参考代码如下：
void InOrderTraverse(BinaryTreeNode * pRoot){if(pRoot == NULL)return;InOrderTraverse(pRoot->m_pLeft); // 中序遍历左子树printf(“%d\n”,pRoot->data); // 显示结点数据InOrderTraverse(pRoot->m_pRight); // 中序遍历右子树}
后序遍历递归解法 （1）如果二叉树为空，空操作。 （2）如果二叉树不为空，先遍历左子树，然后遍历右子树，访问根节点 参考代码如下：
void InOrderTraverse(BinaryTreeNode * pRoot){if(pRoot == NULL)return;InOrderTraverse(pRoot->m_pLeft); // 后序遍历左子树InOrderTraverse(pRoot->m_pRight); // 后序遍历右子树printf(“%d\n”,pRoot->data); // 显示结点数据}4、分层遍历二叉树（按层次从上往下，从左往右）
相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。
void LevelTraverse(BinaryTreeNode * pRoot){if(pRoot == NULL)return;queue<BinaryTreeNode *> q;q.push(pRoot);while(!q.empty()){BinaryTreeNode * pNode = q.front();q.pop();Visit(pNode); // 访问节点if(pNode->m_pLeft != NULL)q.push(pNode->m_pLeft);if(pNode->m_pRight != NULL)q.push(pNode->m_pRight);}return;}5、将二叉查找树变为有序的双向链表
要求不能创建新节点，，只调整指针。 递归解法： （1）如果二叉树查找树为空，不需要转换，对应双向链表的第一个节点是NULL，最后一个节点是NULL （2）如果二叉查找树不为空： 如果左子树为空，对应双向有序链表的第一个节点是根节点，左边不需要其他操作； 如果左子树不为空，转换左子树，二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点，同时将根节点和左子树转换后的双向有序链 表的最后一个节点连接； 如果右子树为空，对应双向有序链表的最后一个节点是根节点，右边不需要其他操作； 如果右子树不为空，对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点，同时将根节点和右子树转换后的双向有序链表的第一个节点连 接。 参考代码如下：
/参数：pRoot: 二叉查找树根节点指针pFirstNode: 转换后双向有序链表的第一个节点指针pLastNode: 转换后双向有序链表的最后一个节点指针/void Convert(BinaryTreeNode * pRoot, BinaryTreeNode * & pFirstNode, BinaryTreeNode * & pLastNode){}6、求二叉树第K层的节点个数其实，每个人都是幸福的。只是，你的幸福，常常在别人眼里。
