手机制作公章的软件,狼雨seo培训,上海网站优化案例,北京汽车网站建设一文搞定面试中的二叉树问题 版权所有#xff0c;转载请注明出处#xff0c;谢谢#xff01; http://blog.csdn.net/walkinginthewind/article/details/7518888
树是一种比较重要的数据结构#xff0c;尤其是二叉树。二叉树是一种特殊的树#xff0c;在二叉树中每个节点…一文搞定面试中的二叉树问题 版权所有转载请注明出处谢谢 http://blog.csdn.net/walkinginthewind/article/details/7518888
树是一种比较重要的数据结构尤其是二叉树。二叉树是一种特殊的树在二叉树中每个节点最多有两个子节点一般称为左子节点和右子节点或左孩子和右孩子并且二叉树的子树有左右之分其次序不能任意颠倒。二叉树是递归定义的因此与二叉树有关的题目基本都可以用递归思想解决当然有些题目非递归解法也应该掌握如非递归遍历节点等等。本文努力对二叉树相关题目做一个较全的整理总结希望对找工作的同学有所帮助。
二叉树节点定义如下 struct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; };
相关链接 轻松搞定面试中的链表题目
题目列表
1. 求二叉树中的节点个数 2. 求二叉树的深度 3. 前序遍历中序遍历后序遍历 4.分层遍历二叉树按层次从上往下从左往右 5. 将二叉查找树变为有序的双向链表 6. 求二叉树第K层的节点个数 7. 求二叉树中叶子节点的个数 8. 判断两棵二叉树是否结构相同 9. 判断二叉树是不是平衡二叉树 10. 求二叉树的镜像 11. 求二叉树中两个节点的最低公共祖先节点 12. 求二叉树中节点的最大距离 13. 由前序遍历序列和中序遍历序列重建二叉树 14.判断二叉树是不是完全二叉树
详细解答
1. 求二叉树中的节点个数 递归解法 1如果二叉树为空节点个数为0 2如果二叉树不为空二叉树节点个数 左子树节点个数 右子树节点个数 1 参考代码如下 [cpp] view plaincopy int GetNodeNum(BinaryTreeNode * pRoot) { if(pRoot NULL) // 递归出口 return 0; return GetNodeNum(pRoot-m_pLeft) GetNodeNum(pRoot-m_pRight) 1; } 2. 求二叉树的深度递归解法1如果二叉树为空二叉树的深度为02如果二叉树不为空二叉树的深度 max(左子树深度 右子树深度) 1参考代码如下[cpp] view plaincopy int GetDepth(BinaryTreeNode * pRoot) { if(pRoot NULL) // 递归出口 return 0; int depthLeft GetDepth(pRoot-m_pLeft); int depthRight GetDepth(pRoot-m_pRight); return depthLeft depthRight ? (depthLeft 1) : (depthRight 1); } 3. 前序遍历中序遍历后序遍历前序遍历递归解法1如果二叉树为空空操作2如果二叉树不为空访问根节点前序遍历左子树前序遍历右子树参考代码如下[cpp] view plaincopy void PreOrderTraverse(BinaryTreeNode * pRoot) { if(pRoot NULL) return; Visit(pRoot); // 访问根节点 PreOrderTraverse(pRoot-m_pLeft); // 前序遍历左子树 PreOrderTraverse(pRoot-m_pRight); // 前序遍历右子树 } 中序遍历递归解法1如果二叉树为空空操作。2如果二叉树不为空中序遍历左子树访问根节点中序遍历右子树参考代码如下[cpp] view plaincopy void InOrderTraverse(BinaryTreeNode * pRoot) { if(pRoot NULL) return; InOrderTraverse(pRoot-m_pLeft); // 中序遍历左子树 Visit(pRoot); // 访问根节点 InOrderTraverse(pRoot-m_pRight); // 中序遍历右子树 } 后序遍历递归解法1如果二叉树为空空操作2如果二叉树不为空后序遍历左子树后序遍历右子树访问根节点参考代码如下[cpp] view plaincopy void PostOrderTraverse(BinaryTreeNode * pRoot) { if(pRoot NULL) return; PostOrderTraverse(pRoot-m_pLeft); // 后序遍历左子树 PostOrderTraverse(pRoot-m_pRight); // 后序遍历右子树 Visit(pRoot); // 访问根节点 } 4.分层遍历二叉树按层次从上往下从左往右
相当于广度优先搜索使用队列实现。队列初始化将根节点压入队列。当队列不为空进行如下操作弹出一个节点访问若左子节点或右子节点不为空将其压入队列。 [cpp] view plaincopy void LevelTraverse(BinaryTreeNode * pRoot) { if(pRoot NULL) return; queueBinaryTreeNode * 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最后一个节点是NULL2如果二叉查找树不为空如果左子树为空对应双向有序链表的第一个节点是根节点左边不需要其他操作如果左子树不为空转换左子树二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点同时将根节点和左子树转换后的双向有序链表的最后一个节点连接如果右子树为空对应双向有序链表的最后一个节点是根节点右边不需要其他操作如果右子树不为空对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点同时将根节点和右子树转换后的双向有序链表的第一个节点连接。参考代码如下[cpp] view plaincopy /****************************************************************************** 参数 pRoot: 二叉查找树根节点指针 pFirstNode: 转换后双向有序链表的第一个节点指针 pLastNode: 转换后双向有序链表的最后一个节点指针 ******************************************************************************/ void Convert(BinaryTreeNode * pRoot, BinaryTreeNode * pFirstNode, BinaryTreeNode * pLastNode) { BinaryTreeNode *pFirstLeft, *pLastLeft, * pFirstRight, *pLastRight; if(pRoot NULL) { pFirstNode NULL; pLastNode NULL; return; } if(pRoot-m_pLeft NULL) { // 如果左子树为空对应双向有序链表的第一个节点是根节点 pFirstNode pRoot; } else { Convert(pRoot-m_pLeft, pFirstLeft, pLastLeft); // 二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点 pFirstNode pFirstLeft; // 将根节点和左子树转换后的双向有序链表的最后一个节点连接 pRoot-m_pLeft pLastLeft; pLastLeft-m_pRight pRoot; } if(pRoot-m_pRight NULL) { // 对应双向有序链表的最后一个节点是根节点 pLastNode pRoot; } else { Convert(pRoot-m_pRight, pFirstRight, pLastRight); // 对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点 pLastNode pLastRight; // 将根节点和右子树转换后的双向有序链表的第一个节点连接 pRoot-m_pRight pFirstRight; pFirstRight-m_pLeft pRoot; } return; } 6. 求二叉树第K层的节点个数递归解法1如果二叉树为空或者k1返回02如果二叉树不为空并且k1返回13如果二叉树不为空且k1返回左子树中k-1层的节点个数与右子树k-1层节点个数之和参考代码如下[cpp] view plaincopy int GetNodeNumKthLevel(BinaryTreeNode * pRoot, int k) { if(pRoot NULL || k 1) return 0; if(k 1) return 1; int numLeft GetNodeNumKthLevel(pRoot-m_pLeft, k-1); // 左子树中k-1层的节点个数 int numRight GetNodeNumKthLevel(pRoot-m_pRight, k-1); // 右子树中k-1层的节点个数 return (numLeft numRight); } 7. 求二叉树中叶子节点的个数完全二叉树有2*n-1 个节点,则它的叶子节点数为?
完全二叉树的节点数是奇数,说明此完全二叉树也是满二叉树,也就是说每个内部节点正好都有2个叶结点. 设内部节点数为a,叶节点数为b,结点总数为m,明显有abm (1) 非空满二叉树中所有节点的出度正好等于入度,每个内部节点出度为2,叶节点出度为0,所有节点的出度和为2a根节点入度为0,其他节点的入度为1,所有节点的入度和为ab-1;因此有2aab-1 (2) 由(1),(2)得 b(m1)/2,a(m-1)/2,ba1 也就是说,非空满二叉树的叶节点数正好比内部节点数多1 此完全二叉树的结点总数为2n-1,因此其叶结点数为n. 递归解法
1如果二叉树为空返回02如果二叉树不为空且左右子树为空返回13如果二叉树不为空且左右子树不同时为空返回左子树中叶子节点个数加上右子树中叶子节点个数参考代码如下[cpp] view plaincopy int GetLeafNodeNum(BinaryTreeNode * pRoot) { if(pRoot NULL) return 0; if(pRoot-m_pLeft NULL pRoot-m_pRight NULL) return 1; int numLeft GetLeafNodeNum(pRoot-m_pLeft); // 左子树中叶节点的个数 int numRight GetLeafNodeNum(pRoot-m_pRight); // 右子树中叶节点的个数 return (numLeft numRight); } 8. 判断两棵二叉树是否结构相同
不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。递归解法1如果两棵二叉树都为空返回真2如果两棵二叉树一棵为空另一棵不为空返回假3如果两棵二叉树都不为空如果对应的左子树和右子树都同构返回真其他返回假参考代码如下[cpp] view plaincopy bool StructureCmp(BinaryTreeNode * pRoot1, BinaryTreeNode * pRoot2) { if(pRoot1 NULL pRoot2 NULL) // 都为空返回真 return true; else if(pRoot1 NULL || pRoot2 NULL) // 有一个为空一个不为空返回假 return false; bool resultLeft StructureCmp(pRoot1-m_pLeft, pRoot2-m_pLeft); // 比较对应左子树 bool resultRight StructureCmp(pRoot1-m_pRight, pRoot2-m_pRight); // 比较对应右子树 return (resultLeft resultRight); } 9. 判断二叉树是不是平衡二叉树递归解法1如果二叉树为空返回真2如果二叉树不为空如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1返回真其他返回假参考代码[cpp] view plaincopy bool IsAVL(BinaryTreeNode * pRoot, int height) { if(pRoot NULL) // 空树返回真 { height 0; return true; } int heightLeft; bool resultLeft IsAVL(pRoot-m_pLeft, heightLeft); int heightRight; bool resultRight IsAVL(pRoot-m_pRight, heightRight); if(resultLeft resultRight abs(heightLeft - heightRight) 1) // 左子树和右子树都是AVL并且高度相差不大于1返回真 { height max(heightLeft, heightRight) 1; return true; } else { height max(heightLeft, heightRight) 1; return false; } } 10. 求二叉树的镜像
递归解法1如果二叉树为空返回空2如果二叉树不为空求左子树和右子树的镜像然后交换左子树和右子树参考代码如下[cpp] view plaincopy BinaryTreeNode * Mirror(BinaryTreeNode * pRoot) { if(pRoot NULL) // 返回NULL return NULL; BinaryTreeNode * pLeft Mirror(pRoot-m_pLeft); // 求左子树镜像 BinaryTreeNode * pRight Mirror(pRoot-m_pRight); // 求右子树镜像 // 交换左子树和右子树 pRoot-m_pLeft pRight; pRoot-m_pRight pLeft; return pRoot; } 11. 求二叉树中两个节点的最低公共祖先节点递归解法1如果两个节点分别在根节点的左子树和右子树则返回根节点2如果两个节点都在左子树则递归处理左子树如果两个节点都在右子树则递归处理右子树参考代码如下[cpp] view plaincopy bool FindNode(BinaryTreeNode * pRoot, BinaryTreeNode * pNode) { if(pRoot NULL || pNode NULL) return false; if(pRoot pNode) return true; bool found FindNode(pRoot-m_pLeft, pNode); if(!found) found FindNode(pRoot-m_pRight, pNode); return found; } BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot, BinaryTreeNode * pNode1, BinaryTreeNode * pNode2) { if(FindNode(pRoot-m_pLeft, pNode1)) { if(FindNode(pRoot-m_pRight, pNode2)) return pRoot; else return GetLastCommonParent(pRoot-m_pLeft, pNode1, pNode2); } else { if(FindNode(pRoot-m_pLeft, pNode2)) return pRoot; else return GetLastCommonParent(pRoot-m_pRight, pNode1, pNode2); } } 递归解法效率很低有很多重复的遍历下面看一下非递归解法。非递归解法先求从根节点到两个节点的路径然后再比较对应路径的节点就行最后一个相同的节点也就是他们在二叉树中的最低公共祖先节点参考代码如下[cpp] view plaincopy bool GetNodePath(BinaryTreeNode * pRoot, BinaryTreeNode * pNode, listBinaryTreeNode * path) { if(pRoot pNode) { path.push_back(pRoot); return true; } if(pRoot NULL) return false; path.push_back(pRoot); bool found false; found GetNodePath(pRoot-m_pLeft, pNode, path); if(!found) found GetNodePath(pRoot-m_pRight, pNode, path); if(!found) path.pop_back(); return found; } BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot, BinaryTreeNode * pNode1, BinaryTreeNode * pNode2) { if(pRoot NULL || pNode1 NULL || pNode2 NULL) return NULL; listBinaryTreeNode* path1; bool bResult1 GetNodePath(pRoot, pNode1, path1); listBinaryTreeNode* path2; bool bResult2 GetNodePath(pRoot, pNode2, path2); if(!bResult1 || !bResult2) return NULL; BinaryTreeNode * pLast NULL; listBinaryTreeNode*::const_iterator iter1 path1.begin(); listBinaryTreeNode*::const_iterator iter2 path2.begin(); while(iter1 ! path1.end() iter2 ! path2.end()) { if(*iter1 *iter2) pLast *iter1; else break; iter1; iter2; } return pLast; } 在上述算法的基础上稍加变化即可求二叉树中任意两个节点的距离了。12. 求二叉树中节点的最大距离
即二叉树中相距最远的两个节点之间的距离。递归解法1如果二叉树为空返回0同时记录左子树和右子树的深度都为02如果二叉树不为空最大距离要么是左子树中的最大距离要么是右子树中的最大距离要么是左子树节点中到根节点的最大距离右子树节点中到根节点的最大距离同时记录左子树和右子树节点中到根节点的最大距离。参考代码如下 [cpp] view plaincopy int GetMaxDistance(BinaryTreeNode * pRoot, int maxLeft, int maxRight) { // maxLeft, 左子树中的节点距离根节点的最远距离 // maxRight, 右子树中的节点距离根节点的最远距离 if(pRoot NULL) { maxLeft 0; maxRight 0; return 0; } int maxLL, maxLR, maxRL, maxRR; int maxDistLeft, maxDistRight; if(pRoot-m_pLeft ! NULL) { maxDistLeft GetMaxDistance(pRoot-m_pLeft, maxLL, maxLR); maxLeft max(maxLL, maxLR) 1; } else { maxDistLeft 0; maxLeft 0; } if(pRoot-m_pRight ! NULL) { maxDistRight GetMaxDistance(pRoot-m_pRight, maxRL, maxRR); maxRight max(maxRL, maxRR) 1; } else { maxDistRight 0; maxRight 0; } return max(max(maxDistLeft, maxDistRight), maxLeftmaxRight); } 13. 由前序遍历序列和中序遍历序列重建二叉树
二叉树前序遍历序列中第一个元素总是树的根节点的值。中序遍历序列中左子树的节点的值位于根节点的值的左边右子树的节点的值位于根节点的值的右边。递归解法1如果前序遍历为空或中序遍历为空或节点个数小于等于0返回NULL。2创建根节点。
前序遍历的第一个数据就是根节点的数据在中序遍历中找到根节点的位置可分别得知左子树和右子树的前序和中序遍
历序列重建左右子树。 题目描述 输入某二叉树的前序遍历和中序遍历的结果请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}则重建二叉树并输出它的后序遍历序列。 输入 输入可能包含多个测试样例对于每个测试案例 输入的第一行为一个整数n(1n1000)代表二叉树的节点个数。 输入的第二行包括n个整数(其中每个元素a的范围为(1a1000))代表二叉树的前序遍历序列。 输入的第三行包括n个整数(其中每个元素a的范围为(1a1000))代表二叉树的中序遍历序列。 输出 对应每个测试案例输出一行 如果题目中所给的前序和中序遍历序列能构成一棵二叉树则输出n个整数代表二叉树的后序遍历序列每个元素后面都有空格。 如果题目中所给的前序和中序遍历序列不能构成一棵二叉树则输出”No”。 样例输入 81 2 4 7 3 5 6 84 7 2 1 5 3 8 681 2 4 7 3 5 6 84 1 2 7 5 3 8 6 样例输出 7 4 2 5 8 6 3 1 No 采用递归的方式重构二叉树关键是要考虑到一些特殊情况比如只有根节点的二叉树、只有左子树或只有右子树的二叉树以及二叉树根节点为NULL、前序中序序列不匹配导致不能重构二叉树等。 AC代码如下一直在如何实现判断能否重构二叉树的地方徘徊在九度论坛里大致看了下借鉴了下各位前辈的思路定义一个全局bool变量用来跟踪判断能够重构 [cpp] view plaincopy #includestdio.h #includestdlib.h typedef int ElemType; typedef struct BTNode { ElemType data; struct BTNode *left; struct BTNode *right; }BTNode,*BTree; bool CanReBuild; //用来标示是否能够重构二叉树 /* pre为前序遍历数组inv为中序遍历数组len为数组长度重构二叉树*ppTree */ void RebuildBinaryTree(BTree *ppTree,int *pre,int *inv,int len) { if(p
