找工作的热头已经过去一段时间了，其中的过程想想还是多少有些蛋疼，参加的大大小小的笔试面试还是有那么一些，做到的二叉树的题基本上都感到很亲切，有种似曾相识的感觉，很多不是自己做过的原题就是相似的原型题，大多都可以在《剑指offer》中找到，现在把它总结出来，下面的题摘自《剑指offer》一书，感觉把二叉树的题见得多了，树的题就大同小异了，这点自己有点体会，以前都没有去准备过树，但是有次做到的一道树的大题，自己居然可以解决掉，还有就是弄二叉树的同时有把递归加深一把了，，囧……
二叉树的结点定义均如下：
class BinaryTreeNode{intm_nValue;BinaryTreeNode*m_pLeft;BinaryTreeNode*m_pRight;};一：重建二叉树
问题描述：输入一颗二叉树的前序遍历序列（如：{1,2,4,7,3,5,6,8}）和中序遍历序列（如：{4,7,2,1,5,3,8,6}，重建出此二叉树。
BinaryTreeNode* Construct(int* preorder, int* inorder, int length){if(preorder == NULL || inorder == NULL || length <= 0)return NULL;return ConstructCore(preorder, preorder + length – 1,inorder, inorder + length – 1);}BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder,int* startInorder, int* endInorder){// 前序遍历序列的第一个数字是根结点的值int rootValue = startPreorder[0];BinaryTreeNode* root = new BinaryTreeNode();root->m_nValue = rootValue;root->m_pLeft = root->m_pRight = NULL;if(startPreorder == endPreorder){if(startInorder == endInorder && *startPreorder == *startInorder)return root;elsethrow std::exception("Invalid input.");}// 在中序遍历中找到根结点的值int* rootInorder = startInorder;while(rootInorder <= endInorder && *rootInorder != rootValue)++ rootInorder;if(rootInorder == endInorder && *rootInorder != rootValue)throw std::exception("Invalid input.");int leftLength = rootInorder – startInorder;int* leftPreorderEnd = startPreorder + leftLength;if(leftLength > 0){// 构建左子树root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd,startInorder, rootInorder – 1);}if(leftLength < endPreorder – startPreorder){// 构建右子树root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder,rootInorder + 1, endInorder);}return root;}二：树的子结构
问题描述：输入两颗二叉树A和B，判断B是不是A的子结构。
bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2){bool result = false;if(pRoot1 != NULL && pRoot2 != NULL){if(pRoot1->m_nValue == pRoot2->m_nValue)result = DoesTree1HaveTree2(pRoot1, pRoot2);if(!result)result = HasSubtree(pRoot1->m_pLeft, pRoot2);if(!result)result = HasSubtree(pRoot1->m_pRight, pRoot2);}return result;}bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2){if(pRoot2 == NULL)return true;if(pRoot1 == NULL)return false;if(pRoot1->m_nValue != pRoot2->m_nValue)return false;return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) &&DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);}三：二叉树的镜像
问题描述：输入一颗二叉树，输出它的镜像。（对着镜子想一下就知道怎么回事了）
void MirrorRecursively(BinaryTreeNode *pNode){if((pNode == NULL) || (pNode->m_pLeft == NULL && pNode->m_pRight))return;BinaryTreeNode *pTemp = pNode->m_pLeft;pNode->m_pLeft = pNode->m_pRight;pNode->m_pRight = pTemp;if(pNode->m_pLeft)MirrorRecursively(pNode->m_pLeft);if(pNode->m_pRight)MirrorRecursively(pNode->m_pRight); }void MirrorIteratively(BinaryTreeNode* pRoot){if(pRoot == NULL)return;std::stack<BinaryTreeNode*> stackTreeNode;stackTreeNode.push(pRoot);while(stackTreeNode.size() > 0){BinaryTreeNode *pNode = stackTreeNode.top();stackTreeNode.pop();BinaryTreeNode *pTemp = pNode->m_pLeft;pNode->m_pLeft = pNode->m_pRight;pNode->m_pRight = pTemp;if(pNode->m_pLeft)stackTreeNode.push(pNode->m_pLeft);if(pNode->m_pRight)stackTreeNode.push(pNode->m_pRight);}}四：从上往下打印二叉树
问题描述：按层次打印二叉树的所有节点。
void PrintFromTopToBottom(BinaryTreeNode* pTreeRoot){if (!pTreeRoot)return;std::deque<BinaryTreeNode *> dequeTreeNode;dequeTreeNode.push_back(pTreeRoot);while (dequeTreeNode.size()){BinaryTreeNode *pNode = dequeTreeNode.front();dequeTreeNode.pop_front();printf ("%d ", pNode ->m_nValue);if (pNode ->m_pLeft)dequeTreeNode.push_back(pNode ->m_pLeft);if (pNode ->m_pRight)dequeTreeNode.push_back(pNode ->m_pRight);}}五：二叉搜索树的后序遍历序列
问题描述：输入一个整数数组（任意两个数字不相同），判断该数组是不是某二叉搜索树的后序遍历的结果。
// BST：Binary Search Tree，二叉搜索树bool VerifySquenceOfBST(int sequence[], int length){if(sequence == NULL || length <= 0)return false;int root = sequence[length – 1];// 在二叉搜索树中左子树的结点小于根结点int i = 0;for(; i < length – 1; ++ i){if(sequence[i] > root)break;}// 在二叉搜索树中右子树的结点大于根结点int j = i;for(; j < length – 1; ++ j){if(sequence[j] < root)return false;}// 判断左子树是不是二叉搜索树bool left = true;if(i > 0)left = VerifySquenceOfBST(sequence, i);// 判断右子树是不是二叉搜索树bool right = true;if(i < length – 1)right = VerifySquenceOfBST(sequence + i, length – i – 1);return (left && right);}六：二叉树中和为某一值的路径
问题描述：输入一棵二叉树和一个整数，打印出二叉树中节点值的和为该整数的路径，根节点到叶节点形成一条路径。
忘掉失败，不过要牢记失败中的教训。
