二叉树常见面试题

相关推荐

二叉树常见面试题

二叉树作为树的一种，是一种重要的数据结构，也是面试官经常考的东西。昨天看了一下关于树中的面试题，发现二叉树中的面试题比较常见的题型大概有下面几个：创建一颗二叉树（先序，中序，后序）、遍历一颗二叉树（先序，中序，后序和层次遍历）、求二叉树中叶子节点的个数、求二叉树的高度、求二叉树中两个节点的最近公共祖先、打印和为某一值的全部路径、求某一节点是否在一个树中等等。

二叉树常见面试题

再详细的说这些面试题之前，不妨先看一下几种常见的二叉树：

完全二叉树：若二叉树的高度是h，除第h层之外，其他（1~h-1）层的节点数都达到了最大个数，并且第h层的节点都连续的集中在最左边。想到点什么没？实际上，完全二叉树和堆联系比较紧密哈~~~

满二叉树： 除最后一层外，每一层上的所有节点都有两个子节点，最后一层都是叶子节点。

哈夫曼树：又称为最有数，这是一种带权路径长度最短的树。哈夫曼编码就是哈夫曼树的应用。

平衡二叉树：所谓平衡二叉树指的是，左右两个子树的高度差的绝对值不超过 1。

红黑树：红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）。

二叉树中的那些面试题

再具体说二叉树中的那些面试题之前，我们先看一下二叉树中的每个节点是什么样的，以及为了完成这些面试题，二叉树中声明的函数原型是什么样的：

二叉树的节点：BinTreeNode

View Code1//二叉树的节点类2classBinTreeNode3{4private:5intdata;6BinTreeNode *left,*right;7public:8//利用初始化列表完成data，left，rightn的初始化9BinTreeNode(constint&item,BinTreeNode *lPtr = NULL,BinTreeNode *rPtr =NULL):data(item) ,left(lPtr),right(rPtr){};10voidset_data(intitem)11{12data =item;13}14intget_data()const15{16returndata;17}18voidset_left(BinTreeNode *l)19{20left =l;21}22BinTreeNode* get_left()const23{24returnleft;25}26voidset_right(BinTreeNode *r)27{28right =r;29}30BinTreeNode* get_right()const31{32returnright;33}34};

二叉树原型：BinTree，其中包含了这篇文章中要完成的函数原型的完整声明。

View Code1//二叉树2classBinTree3{4private:5BinTreeNode *root;6public:7BinTree(BinTreeNode *t =NULL):root(t){};8~BinTree(){delete root;};9voidset_root(BinTreeNode *t)10{11root =t;12}13BinTreeNode* get_root()const14{15returnroot;16}17//1.创建二叉树18BinTreeNode*create_tree();19//2.前序遍历20voidpre_order(BinTreeNode *r)const;21//3.中序遍历22voidin_order(BinTreeNode *r)const;23//4.后序遍历24voidpost_order(BinTreeNode *r)const;25//5.层次遍历26voidlevel_order(BinTreeNode *r)const;27//6.获得叶子节点的个数28intget_leaf_num(BinTreeNode *r)const;29//7.获得二叉树的高度30intget_tree_height(BinTreeNode *r)const;31//8.交换二叉树的左右儿子32voidswap_left_right(BinTreeNode *r);33//9.求两个节点pNode1和pNode2在以r为树根的树中的最近公共祖先34BinTreeNode* get_nearest_common_father(BinTreeNode *r,BinTreeNode *pNode1,BinTreeNode *pNode2)const;35//10.打印和为某一值的所有路径36voidprint_rout(BinTreeNode *r,intsum)const;37//11.判断一个节点t是否在以r为根的子树中38boolis_in_tree(BinTreeNode *r,BinTreeNode *t)const;39};

2.1 创建一颗二叉树

创建一颗二叉树，可以创建先序二叉树，中序二叉树，后序二叉树。我们在创建的时候为了方便，不妨用‘#’表示空节点，这时如果先序序列是：6 4 2 3 # # # # 5 1 # # 7 # #，那么创建的二叉树如下：

下面是创建二叉树的完整代码：穿件一颗二叉树，返回二叉树的根。

View Code1//创建二叉树，这里不妨使用前序创建二叉树，遇到‘#’表示节点为空2BinTreeNode*BinTree::create_tree()3{4charitem;5BinTreeNode *t,*t_l,*t_r;6cin>>item;7if(item !='#')8{9BinTreeNode *pTmpNode =newBinTreeNode(item-48);10t =pTmpNode;11t_l =create_tree();12t->set_left(t_l);13t_r =create_tree();14t->set_right(t_r);15returnt;16}17else18{19t =NULL;20returnt;21}22}

2.2 二叉树的遍历

二叉树的遍历分为：先序遍历，中序遍历和后序遍历，这三种遍历的写法是很相似的，利用递归程序完成也是灰常简单的：

View Code1//前序遍历2voidBinTree::pre_order(BinTreeNode *r)const3{4BinTreeNode *pTmpNode =r;5if(pTmpNode !=NULL)6{7cout<<pTmpNode->get_data()<<"";8pre_order(pTmpNode->get_left());9pre_order(pTmpNode->get_right());10}11}12//中序遍历13voidBinTree::in_order(BinTreeNode *r)const14{15BinTreeNode *pTmpNode =r;16if(pTmpNode !=NULL)17{18in_order(pTmpNode->get_left());19cout<<pTmpNode->get_data()<<"";20in_order(pTmpNode->get_right());21}22}23//后序遍历24voidBinTree::post_order(BinTreeNode *r)const25{26BinTreeNode *pTmpNode =r;27if(pTmpNode !=NULL)28{29post_order(pTmpNode->get_left());30post_order(pTmpNode->get_right());31cout<<pTmpNode->get_data()<<"";32}33}

2.3 层次遍历

层次遍历也是二叉树遍历的一种方式，二叉树的层次遍历更像是一种广度优先搜索（BFS）。因此二叉树的层次遍历利用队列来完成是最好不过啦，当然不是说利用别的数据结构不能完成。

View Code1//层次遍历2voidBinTree::level_order(BinTreeNode *r)const3{4if(r ==NULL)5return;6deque<BinTreeNode*>q;7q.push_back(r);8while(!q.empty())9{10BinTreeNode *pTmpNode =q.front();11cout<<pTmpNode->get_data()<<"";12q.pop_front();13if(pTmpNode->get_left() !=NULL)14{15q.push_back(pTmpNode->get_left());16}17if(pTmpNode->get_right() !=NULL)18{19q.push_back(pTmpNode->get_right());20}21}22}

2.4 求二叉树中叶子节点的个数

树中的叶子节点的个数 = 左子树中叶子节点的个数 + 右子树中叶子节点的个数。利用递归代码也是相当的简单，易懂。

View Code1//获取叶子节点的个数2intBinTree::get_leaf_num(BinTreeNode *r)const3{4if(r == NULL)//该节点是空节点，比如建树时候用'#'表示5{6return0;7}8if(r->get_left()==NULL && r->get_right()==NULL)//该节点并不是空的，但是没有孩子节点9{10return1;11}12//递归整个树的叶子节点个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数13returnget_leaf_num(r->get_left()) + get_leaf_num(r->get_right());14}

2.5 求二叉树的高度

求二叉树的高度也是非常简单，不用多说：树的高度 = max(左子树的高度，右子树的高度) + 1 。

View Code1//获得二叉树的高度2intBinTree::get_tree_height(BinTreeNode *r)const3{4if(r == NULL)//节点本身为空5{6return0;7}8if(r->get_left()==NULL && r->get_right()==NULL)//叶子节点9{10return1;11}12intl_height = get_tree_height(r->get_left());13intr_height = get_tree_height(r->get_right());14returnl_height >= r_height ? l_height +1: r_height +1;15}

2.6 交换二叉树的左右儿子

交换二叉树的左右儿子，可以先交换根节点的左右儿子节点，然后递归以左右儿子节点为根节点继续进行交换。树中的操作有先天的递归性。。

View Code1//交换二叉树的左右儿子2voidBinTree::swap_left_right(BinTreeNode *r)3{4if(r ==NULL)5{6return;7}8BinTreeNode *pTmpNode = r->get_left();9r->set_left(r->get_right());10r->set_right(pTmpNode);11swap_left_right(r->get_left());12swap_left_right(r->get_right());13}

2.7 判断一个节点是否在一颗子树中

可以和当前根节点相等，也可以在左子树或者右子树中。

View Code1//判断一个节点t是否在以r为根的子树中2boolBinTree::is_in_tree(BinTreeNode *r,BinTreeNode *t)const3{4if(r ==NULL)5{6returnfalse;7}8elseif(r ==t)9{10returntrue;11}12else13{14boolhas =false;15if(r->get_left() !=NULL)16{17has = is_in_tree(r->get_left(),t);18}19if(!has && r->get_right()!=NULL)20{21has = is_in_tree(r->get_right(),t);22}23returnhas;24}25}

2.8 求两个节点的最近公共祖先

求两个节点的公共祖先可以用到上面的：判断一个节点是否在一颗子树中。（1）如果两个节点同时在根节点的右子树中，则最近公共祖先一定在根节点的右子树中。（2）如果两个节点同时在根节点的左子树中，则最近公共祖先一定在根节点的左子树中。（3）如果两个节点一个在根节点的右子树中，一个在根节点的左子树中，则最近公共祖先一定是根节点。当然，要注意的是：可能一个节点pNode1在以另一个节点pNode2为根的子树中，这时pNode2就是这两个节点的最近公共祖先了。显然这也是一个递归的过程啦：

View Code1//求两个节点的最近公共祖先2BinTreeNode* BinTree::get_nearest_common_father(BinTreeNode *r,BinTreeNode *pNode1,BinTreeNode *pNode2)const3{4//pNode2在以pNode1为根的子树中（每次递归都要判断，放在这里不是很好。）5if(is_in_tree(pNode1,pNode2))6{7returnpNode1;8}9//pNode1在以pNode2为根的子树中10if(is_in_tree(pNode2,pNode1))11{12returnpNode2;13}14boolone_in_left,one_in_right,another_in_left,another_in_right;15one_in_left = is_in_tree(r->get_left(),pNode1);16another_in_right = is_in_tree(r->get_right(),pNode2);17another_in_left = is_in_tree(r->get_left(),pNode2);18one_in_right = is_in_tree(r->get_right(),pNode1);19if((one_in_left && another_in_right) || (one_in_right &&another_in_left))20{21returnr;22}23elseif(one_in_left &&another_in_left)24{25returnget_nearest_common_father(r->get_left(),pNode1,pNode2);26}27elseif(one_in_right &&another_in_right)28{29returnget_nearest_common_father(r->get_right(),pNode1,pNode2);30}31else32{33returnNULL;34}35}

可以看到这种做法，进行了大量的重复搜素，其实有另外一种做法，那就是存储找到这两个节点的过程中经过的所有节点到两个容器中，然后遍历这两个容器，第一个不同的节点的父节点就是我们要找的节点啦。实际上这还是采用了空间换时间的方法。

2.9 从根节点开始找到所有路径，使得路径上的节点值和为某一数值（路径不一定以叶子节点结束）

这道题要找到所有的路径，显然是用深度优先搜索（DFS）啦。但是我们发现DFS所用的栈和输出路径所用的栈应该不是一个栈，栈中的数据是相反的。看看代码：注意使用的两个栈。

View Code1//注意这两个栈的使用2stack<BinTreeNode *>dfs_s;3stack<BinTreeNode *>print_s;4//打印出从r开始的和为sum的所有路径5voidBinTree::print_rout(BinTreeNode *r,intsum)const6{7if(r ==NULL)8{9return;10}11//入栈12sum -= r->get_data();13dfs_s.push(r);14if(sum <=0)15{16if(sum ==0)17{18while(!dfs_s.empty())19{20print_s.push(dfs_http://www.ahsrst.cn());21dfs_s.pop();22}23while(!print_s.empty())24{25cout<<print_http://www.ahsrst.cn()->get_data()<<"";26dfs_s.push(print_http://www.ahsrst.cn());27print_s.pop();28}29cout<<endl;30}31sum += r->get_data();32dfs_s.pop();33return;34}35//递归进入左子树36print_rout(r->get_left(),sum);37//递归进入右子树

常见的二叉树面试题2015-09-07 17:18 | #2楼

二叉树面试题

面试中，最常见是数据结构就是二叉树和链表了，其中和二叉树有关的常见面试题主要是：树的前序遍历、中序遍历、后序遍历、分层遍历、树的节点数、树的叶子节点数、树的第K层节点数、树的深度、树的宽度、平衡二叉树的判定、完全二叉树的判定、满二叉树的判定、由前序中序反推后序遍历、由前序中序重建二叉树，处理这些问题基本思想无外乎是“遍历+递归”。

关于树的遍历，递归方式太傻太天真，但也是最基本的思想，实现代码网上资料可谓是汗牛充栋，在此就不赘述了。

下面仅列举了非递归实现树的前序、中序以及后序遍历，由于笔者对代码有洁癖，最不能忍受一个while循环里再嵌套另外一个while循环（网上千篇一律的实现代码方式），虽然二者的思想都是一致的，但笔者的实现方式更为直观易懂，故此处的版本都只借助一个栈、一个while循环：

前序非递归遍历：

void PreOrderTraseNonRecursion(BTree* t){stack<BNode*> s;s.push(t);while(!s.empty()){BNode* p = http://www.ahsrst.cn();s.pop();Visit(p);if(p->rchild)s.push(p->rchild);if(p->lchild)s.push(p->lchild);}}

中序非递归遍历：

void InOrderTraseNonRecursion(BTree* t){stack<BNode*> s;BNode* p=t;while(p||!s.empty()){if(p){s.push(p);p=p->lchild;}else{p = http://www.ahsrst.cn();s.pop();Visit(p);p=p->rchild;}}}前序和中序的非递归遍历都很好理解，我就不再浪费口舌笔墨了，要是真看不懂，请回去把严蔚敏那本《数据结构》再啃一遍、两遍、三遍……要是还看不懂，我只能怀着无比沉重的心情告诉你一个非常不幸的消息：“对不起，你不适合这个行业！”

后序非递归遍历： 后序非递归遍历稍微比较难理解些，但是你如果对前序和中序遍历思想已经融会贯通了，其实也就那样：

从根节点开始，只要当前节点存在，或者栈不为空，则重复下面操作：

(1)从当前节点开始，进栈并走左子树，直到左子树为空。

(2)如果栈顶节点的右子树为空，或者栈顶节点的右孩子为刚访问过的节点，

则退栈并访问，然后置当前节点指针为空。

(3)否则走右子树。

void PostOrderTraseNonRecursion(BTree* t){stack<BNode*> s;BNode* p=t;BNode* q=NULL;while(p||!s.empty()){if(p){s.push(p);p=p->lchild;}else{p = http://www.ahsrst.cn();if(p->rchild==NULL || p->rchild==q){Visit(p);s.pop();q = p;p = NULL;}else{p=p->rchild;}}}}还有一种网上流传的后序遍历的方式是借助于两个栈，一个栈用来遍历，另一个栈保存遍历到的结点，最后一起出栈，就是后序遍历结果。

void PostOrderTraseNonRecursion2(BTree* t) { stack<BNode*> sTraverse,sVisit; BNode* p=NULL; if(t==NULL) return; sTraverse.push(t); while(!sTraverse.empty()) { p=http://www.ahsrst.cn(); sTraverse.pop(); sVisit.push(p); if(p->lchild) sTraverse.push(p->lchild); if(p->rchild) sTraverse.push(p->rchild); } while(!sVisit.empty()) { p=http://www.ahsrst.cn(); sVisit.pop(); Visit(p);} }

分层遍历： 通过分层遍历可实现统计树的深度、每一层节点数、树的最大宽度等要求。基本解法想必你也知道了，就是借助一个队列，进行入队、出队操作，如下面的二叉树，要是一口气全部打印所有节点，即输出：

1 2 3 4 5 6 7 。

再进一步考察，如何实现将二叉树按层打印，即每一行打印二叉树的每一层树节点，输出为：

1 2 3 4 5 6 7 1

/ \

2 3

/ \ \

4 5 6

/ 7

这就需要再基本的分层遍历基础上再做些手脚了，下面是一个简单的例子：

//分层打印节点，每一行为一层，返回该二叉树的层数int DepthTrase(BTree* t){if(t==NULL)return 0;vector<BNode*> v;v.push_back(t);int front=0;//该层的开始节点下标int rear=0;//该层结束节点下标int last=1;//所有已遍历的节点个数int level=0;//层次数while(rear < v.size()){BNode* p = v[rear++];if(p->lchild)v.push_back(p->lchild);if(p->rchild)v.push_back(p->rchild);if(rear>=last){//打印每一层节点for(int i=front;i<rear;++i){Visit(v[i]);}cout<<endl; //重置为下一层遍历准备front=rear;last=v.size();level++;}}return level;}

【二叉树常见面试题】相关文章：

10个常见的压力面试题及回答05-01

常见医院面试题目与参考答案05-01

面试施工员要注意什么？常见面试题有哪些？06-09

外企面试题05-01

面试题目精选05-01

高职面试题目03-03