二叉树的经典面试题总结

1、二叉树的构造

#include <iostream> #include <cassert> #include <queue> #include <stack> using namespace std; template <class T> struct TreeNode { TreeNode(const T& value = T()) :_value(value) ,_lchild(0) ,_rchild(0) {} T _value;//节点的值 TreeNode<T>* _lchild;//左孩子 TreeNode<T>* _rchild;//右孩子 }; template <class T> class BinaryTree { public: typedef TreeNode<T> Node; BinaryTree()//无参构造函数 :_root(NULL) {} BinaryTree(const T* a,size_t size,const T& invalid)//构造函数 { assert(a); size_t index = 0; _root = CreatTree(a,size,invalid,index); } BinaryTree(const BinaryTree<T>& b)//拷贝构造 { _root = Copy(b._root); } //现代写法的赋值运算符重载1 BinaryTree& operator=(const BinaryTree<T>& b) { if (this != &b) { Node* tmp = Copy(b._root); Destroy(_root) ; _root = tmp; //swap(_root,tmp); } return *this; } 现代写法的赋值运算符重载2 //BinaryTree& operator=(BinaryTree<T> b) //{ // swap(b._root,_root); // return *this; //} ~BinaryTree()//析构 { if (NULL != _root) { Destroy(_root); _root = NULL; } } protected: //按照先序遍历递归建树 Node* CreatTree(const T* a,size_t size,const T& invalid,size_t& index)//注意index的传值方式 { assert(a); Node* root = NULL; if (a[index] != invalid && index < size)//按先序遍历建树 { root = new Node(a[index]); root->_lchild = CreatTree(a,size,invalid,++index); root->_rchild = CreatTree(a,size,invalid,++index); } return root; } //拷贝对象 Node* Copy(Node* root) { Node* tmp = NULL; if(root) { tmp = new Node(root->_value); tmp->_lchild = Copy(root->_lchild); tmp->_rchild = Copy(root->_rchild); } return tmp; } //释放空间 void Destroy(Node*& root) { if(root)//用后序遍历方式释放空间 { Destroy(root->_rchild); Destroy(root->_lchild); delete root; root = NULL; } } private: Node* _root;//根节点 };

2、遍历二叉树 二叉树的遍历方式一共分为四种：先序遍历、中序遍历、后序遍历和层序遍历，而前三种遍历又分为递归遍历和非递归遍历，层序遍历则是借助队列先进先出的特性来辅助完成。 【递归遍历二叉树】

void preorder(Node* root)//先序遍历打印树的各个节点 { if (root) { cout<<root->_value<<" "; //访问当前节点的值 preorder(root->_lchild); //递归遍历左子树 preorder(root->_rchild); //递归遍历右子树 } } void inorder(Node* root)//中序遍历打印树的各个节点 { if (root) { preorder(root->_lchild); //递归遍历左子树 cout<<root->_value<<" "; //访问当前节点的值 preorder(root->_rchild); //递归遍历右子树 } } void postorder(Node* root)//后序遍历打印树的各个节点 { if (root) { preorder(root->_lchild); //递归遍历左子树 preorder(root->_rchild); //递归遍历右子树 cout<<root->_value<<" "; //访问当前节点的值 } } void levelorder(Node* root)//层序遍历打印树的各个节点 { queue<Node*> q; if (root) { q.push(root);//将根节点插进队列 } while(!q.empty()) { Node* front = q.front(); q.pop(); cout<<front->_value<<" "; if (front->_lchild) { q.push(front->_lchild); } if (front->_rchild) { q.push(front->_rchild); } } }

【非递归遍历二叉树】 提供给外部的接口：

public: void PreOrder()//先序遍历打印树的各个节点 { cout<<"先序遍历:"; preorderR(_root); cout<<endl; } void InOrder()//中序遍历打印树的各个节点 { cout<<"中序遍历:"; inorderR(_root); cout<<endl; } void PostOrder()//后序遍历打印树的各个节点 { cout<<"后序遍历:"; postorderR(_root); cout<<endl; } void LevelOrder()//层序遍历打印树的各个节点 { cout<<"层序遍历:"; levelorder(_root); cout<<endl; }

算法实现：

void preorderR(Node* root)//先序遍历打印树的各个节点 { Node* cur = root; stack<Node*> s; while (!s.empty() || cur)//只要当前节点和栈不同时为空，就说明树没遍历完 { while(cur)//先序遍历，遇到树根节点直接访问数据并将其压栈 { cout<<cur->_value<<" "; s.push(cur); cur = cur->_lchild; } Node* top = s.top();//取出栈顶元素，到此说明此节点以及其左子树已经访问过了 s.pop(); cur = top->_rchild;//以子问题的方式去访问右子树 } cout<<endl; } void inorderR(Node* root)//中序遍历打印树的各个节点 { Node* cur = root; stack<Node*> s; while(!s.empty() || cur)//只要当前节点和栈不同时为空，就说明树没遍历完 { while(cur)//中序遍历，遇到树根节点直接将其压栈 { s.push(cur); cur = cur->_lchild; } Node* top = s.top();//取出栈顶元素，到此说明此节点的左子树已经访问过了 cout<<top->_value<<" ";//访问栈顶元素（即根节点） s.pop(); cur = top->_rchild;//以子问题的方式去访问右子树 } cout<<endl; } void postorderR(Node* root)//后序遍历打印树的各个节点 { Node* cur = root; Node* prev = NULL;//上一个访问过的数据 stack<Node*> s; while(!s.empty() || cur)//只要当前节点和栈不同时为空，就说明树没遍历完 { //后序遍历，遇到树根节点直接将其压栈 while(cur) { s.push(cur); cur = cur->_lchild; } Node* top = s.top();//取栈顶元素，但不一定能访问 //当节点右子树为空或已经访问过时对其直接进行访问 if (top->_rchild==NULL || top->_rchild==prev) { cout<<top->_value<<" "; prev = top;//将prev更新为已经访问的节点 s.pop(); } else//以子问题的方式去访问右子树 { cur = top->_rchild; } } cout<<endl; } void levelorder(Node* root)//层序遍历打印树的各个节点 { queue<Node*> q; if (root) { q.push(root);//将根节点插进队列 } while(!q.empty()) { Node* front = q.front(); q.pop(); cout<<front->_value<<" "; if (front->_lchild) { q.push(front->_lchild); } if (front->_rchild) { q.push(front->_rchild); } } }

3、求二叉树的高度（深度） 外部接口：

size_t Depth()//求树的深度 { cout<<"depth:"; return depth(_root); }

算法实现：

size_t depth(Node* root)//求树的深度 { if (NULL == root) { return 0; } else { return depth(root->_lchild)>depth(root->_rchild)? (depth(root->_lchild)+1):(depth(root->_rchild)+1); } }

4、求二叉树中节点的个数 外部接口：

size_t Size()//求树中的节点个数 { cout<<"size:"; return size(_root); }

算法实现：

size_t size(Node* root)//求树中的节点个数 { size_t count = 0; if (NULL == root) { count = 0; } else { //当前节点 = 左子树节点 + 右子树节点 + 1 count = size(root->_lchild) + size(root->_rchild)+ 1; } return count; }

5、求二叉树中叶子节点的个数 外部接口：

size_t GetLeafSize() { cout<<"leaf_size:"; return getleafsize(_root); }

算法实现：

size_t getleafsize(Node* root)//求叶节点的个数 { if (NULL == root)//空树 { return 0; } if (NULL == root->_lchild && NULL == root->_rchild)//左叶节点右节点均为空，即 { return 1; } else//左子树的叶节点+右子树的叶节点 { return getleafsize(root->_lchild)+getleafsize(root->_rchild); } }

6、求二叉树第K层的节点个数（假设根节点为第1层） 外部接口：

size_t GetKLevelSize(size_t k)//树中第k层的节点个数 { cout<<k<<"_level_size:"; return getklevelsize(_root,k); }

算法实现：

size_t getklevelsize(Node* root,size_t k)//树中第k层的节点个数 { assert(k>0); size_t count = 0; if (NULL == root) { return 0; } if (k == 1) { count++; } else { count = getklevelsize(root->_lchild,k-1) + getklevelsize(root->_rchild,k-1); } return count; }

7、判断一个节点是否在二叉树中 外部接口：

bool Find(const T& data) //判断一个值为的节点是否在当前二叉树中 { return _Find(_root,data); }

算法实现：

bool _Find(Node* root,const T& data) //查找指定数据的节点 { if (NULL == root) { return false; } else if (root->_data == data) { return true; } else { bool isIn = false; if (root->_left && !isIn) isIn = _Find(root->_left,data); if (root->_right && !isIn) isIn = _Find(root->_right,data); return isIn; } }

8、求两个节点的最近公共祖先 外部接口：

Node* sameAncester(Node* n1,Node* n2) //求两个节点的最近公共祖先 { //return _sameAncester1(_root,n1,n2); //return _sameAncester2(_root,n1,n2); return _sameAncester3(_root,n1,n2); }

算法实现：

Node* _sameAncester1(Node*& root,Node* n1,Node* n2)//求两个节点的最近公共祖先(时间复杂度：O(N^2)) { assert(n1 && n2); //保证两个节点都在当前树中,且当前树不为空 if (root && Find(n1->_data) && Find(n2->_data)) { //其中一个节点为根节点，直接返回根节点 if (root->_data == n1->_data || root->_data == n2->_data) { return root; } //两个节点：1、都在左子树 2、都在右子树 3、一个在左子树，一个在右子树 else { Node* cur = root; //在当前树的左子树去找n1和n2节点，如果没找到就一定在右子树 bool tmp1 = _Find(cur->_left,n1->_data); bool tmp2 = _Find(cur->_left,n2->_data); //n1和n2都在左子树 if (tmp1 && tmp2) { return _sameAncester1(cur->_left,n1,n2); } //n1和n2都在右子树 else if(!tmp1 && !tmp2) { return _sameAncester1(cur->_right,n1,n2); } //n1与n2一个在左子树一个在右子树 else { return root; } } } return NULL; } bool _GetPath2(Node* root,Node* cur,stack<Node*>& s)//在根为root的树中查找节点cur的路径 { if (NULL == root || NULL == cur)//树为空 return false; s.push(root); //将当前节点入栈 if (cur->_data == root->_data) //找到路径 { return true; } if (_GetPath2(root->_left,cur,s))//在左子树中找路径 { return true; } if (_GetPath2(root->_right,cur,s))//在右子树中找路径 { return true; } s.pop(); return false; } Node* _sameAncester2(Node*& root,Node* n1,Node* n2)//求两个节点的最近公共祖先(时间复杂度：O(N)) { //树为空 if (NULL == root) { return NULL; } stack<Node*> s1; stack<Node*> s2; //用栈s1和s2分别保存节点n1和节点n2的路径 _GetPath2(root,n1,s1); _GetPath2(root,n2,s2); //将多余的路径删除 while (s1.size() > s2.size()) { s1.pop(); } while(s1.size() < s2.size()) { s2.pop(); } //找s1与s2中不同的节点 while(s1.top() != s2.top()) { s1.pop(); s2.pop(); } return s1.top(); } bool _GetPath3(Node* root,Node* cur,vector<Node*>& v) { if (NULL == root || NULL == cur)//树为空 return false; v.push_back(root); if (cur->_data == root->_data) //找到路径 { return true; } else { bool ret = false; if (root->_left && !ret)//在左子树中找路径 { ret = _GetPath3(root->_left,cur,v); } if (root->_right && !ret)//在右子树中找路径 { ret = _GetPath3(root->_right,cur,v); } if (ret == false && v.size() != 0)//如果不是正确路径上的节点，就去除该节点 { v.pop_back(); } return ret; } } Node* _sameAncester3(Node*& root,Node* n1,Node* n2) { //树为空 if (NULL == root) { return NULL; } //定义容器 vector<Node*> v1; vector<Node*> v2; //用容器v1和v2分别保存节点n1和节点n2的路径 _GetPath3(root,n1,v1); _GetPath3(root,n2,v2); 从下往上找 定义指向查找节点的迭代器指针 //vector<Node*>::iterator it1 = --v1.end(); //vector<Node*>::iterator it2 = --v2.end(); 将多余的路径节点删除掉 //while(v1.size() > v2.size()) //{ // --it1; //相应的迭代器要向前移 // v1.pop_back(); //} //while(v2.size() > v1.size()) //{ // --it2; //相应的迭代器要向前移 // v2.pop_back(); //} 找v1与v2中不同的节点 //while(it1 >= v1.begin() && it2 >= v2.begin()) //{ // if (*it1 == *it2) // { // return *it1; // } // --it1; // --it2; //} //从上往下找 //定义指向查找节点的迭代器指针 vector<Node*>::iterator it1 = v1.begin(); vector<Node*>::iterator it2 = v2.begin(); //找v1与v2中不同的节点 while(it1 != v1.end() && it2 != v2.end()) { if (*it1 != *it2)//找到第一个不相同的节点，返回前一个节点 { return *(--it1); } ++it1; ++it2; } //处理特殊情况，例如：v1:1->2->3 v2:1->2 if (it1 == v1.end() || it2 == v2.end()) return *(--it1); return NULL; }

9、判断一棵二叉树是否是平衡二叉树 算法实现

bool IsCompleteBT()//判断一棵树是否是完全二叉树 { bool flag = true;//判断一棵子树是否为一棵完全二叉树的标记 queue<Node*> q; //运用队列进行层序遍历 q.push(_root); while(!q.empty()) { Node* front = q.front();//保存队首节点 q.pop(); //将队首元素出队 /*如果队首元素的左树为空，将标志置为false,如果层序遍历\ \后面的节点还有子树，说明不是完全二叉树*/ if (NULL == front->_left) { flag = false; } else { /*如果flag为假，说明之前已经有节点的孩子为空，又因当前\ \节点的左孩子不为空，说明不是完全二叉树*/ if (flag == false) { return false; } q.push(front->_left);//继续向后探索 } /*如果队首元素的右树为空，将标志置为false,如果层序遍历\ \后面的节点还有子树，说明不是完全二叉树*/ if (NULL == front->_right) { flag = false; } else { /*如果flag为假，说明之前已经有节点的孩子为空，又因当前\ \节点的右孩子不为空，说明不是完全二叉树*/ if (flag == false) { return false; } q.push(front->_right);//继续向后探索 } } return true;//能走到这里说明一定是完全二叉树 }

10、求二叉树中最远的两个节点的距离 外部接口：

int RemoteDistance() //求二叉树中最远的两个节点的距离 { int tmp = 0; return _RemoteDistance1(_root,tmp); }

算法实现：

int _RemoteDistance1(Node* root,int& distance) { if (NULL == root) { return 0; } int tmp = _Depth(root->_left)+_Depth(root->_right);//递归去求每棵子树的最远距离 if (distance < tmp)//用全局变量保存每棵子树的最远距离，并不断更新 { distance = tmp; } return distance; }

11、由前序遍历和中序遍历重建二叉树 外部接口：

Node* Rebuild(T* prevOrder,T* inOrder,int n) //根据前序序列和中序序列重建二叉树 { assert(prevOrder && inOrder); int prevIndex = 0; //指向前序序列指针的下标 int inBegin = 0; //中序序列的首位置的下标 int inEnd = n-1; //中序序列的末位置的下标(闭区间) _root = _Rebuild(prevOrder,prevIndex,inOrder,inBegin,inEnd,n); return _root; }

算法实现：

Node* _Rebuild(T* prevOrder,int& prevIndex,T* inOrder,int inBegin,int inEnd,int n) { Node* root = NULL; if (prevIndex < n)//当前序序列的下标<n时才创建新结点 { root = new Node(prevOrder[prevIndex]); } if (NULL == root)//递归的返回条件 { return NULL; } if (inBegin == inEnd)//要重建树中只有一个节点 { return root; } else { //在中序序列中找到前序序列中的根 int i = inBegin; for ( ; i <= inEnd; ++i) { if (prevOrder[prevIndex] == inOrder[i]) break; } if (i > inEnd)//说明中序序列中没找到前序序列中的根，所给序列不匹配 { throw invalid_argument("所给序列不匹配！");//直接抛异常 } //将根节点作为分割线，将区间分为左右两部分，分别递归重建左右子树 root->_left = _Rebuild(prevOrder,++prevIndex,inOrder,inBegin,i-1,n); root->_right = _Rebuild(prevOrder,++prevIndex,inOrder,i+1,inEnd,n); return root; } }

12、判断一棵树是否是完全二叉树 算法实现：

bool IsCompleteBT()//判断一棵树是否是完全二叉树 { bool flag = true;//判断一棵子树是否为一棵完全二叉树的标记 queue<Node*> q; //运用队列进行层序遍历 q.push(_root); while(!q.empty()) { Node* front = q.front();//保存队首节点 q.pop(); //将队首元素出队 /*如果队首元素的左树为空，将标志置为false,如果层序遍历\ \后面的节点还有子树，说明不是完全二叉树*/ if (NULL == front->_left) { flag = false; } else { /*如果flag为假，说明之前已经有节点的孩子为空，又因当前\ \节点的左孩子不为空，说明不是完全二叉树*/ if (flag == false) { return false; } q.push(front->_left);//继续向后探索 } /*如果队首元素的右树为空，将标志置为false,如果层序遍历\ \后面的节点还有子树，说明不是完全二叉树*/ if (NULL == front->_right) { flag = false; } else { /*如果flag为假，说明之前已经有节点的孩子为空，又因当前\ \节点的右孩子不为空，说明不是完全二叉树*/ if (flag == false) { return false; } q.push(front->_right);//继续向后探索 } } return true;//能走到这里说明一定是完全二叉树 }

13、求二叉树的镜像 外部接口：

void GetMirrorTree()//求二叉树的镜像 { _GetMirrorTree(_root); }

算法实现：

void _GetMirrorTree(Node* root)//求二叉树的镜像 { if (NULL == root) { return; } swap(root->_left,root->_right);//交换左右子树 _GetMirrorTree(root->_left); //递归遍历左子树 _GetMirrorTree(root->_right);//递归遍历右子树 }

14、将二叉搜索树转换为一个已排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向 外部接口：

void MakeSearchToList()/*将二叉搜索树转换成一个排序的双向链表。\ 要求不能创建任何新的结点，只能调整树中结点指针的指向。*/ { Node* cur = _root; //寻找最左节点 while (cur->_left) { cur = cur->_left; } Node* prev = NULL; _MakeSearchToList1(_root,prev); //_MakeSearchToList2(_root); while(cur)//打印链表(树的结构变了之后析构会死循环) { cout<<cur->_data<<"<->"; cur = cur->_right; } cout<<"null"; }

算法实现：

void _MakeSearchToList1(Node* root,Node*& prev) { if (NULL == root)//如果当前树为空，则直接返回 return; _MakeSearchToList1(root->_left,prev);//递归左子树 //进行转换 root->_left = prev;//root第一次指向最左节点 if (prev)//如果上一个节点不为空，就将上一个节点的右指针指向当前节点root { prev->_right = root; } prev = root;//更新保存上一个节点 _MakeSearchToList1(root->_right,prev);//递归右子树 } void _InOrderList(Node* root,queue<Node*>& q)//将树的中序遍历的节点入到队列中 { if (NULL == root) return; _InOrderList(root->_left,q);//递归左子树 q.push(root); //将当前节点入队 _InOrderList(root->_right,q);//递归右子树 } void _MakeSearchToList2(Node* root) { if (NULL == root)//如果当前树为空则直接返回 return; queue<Node*> q; _InOrderList(root,q);//将所给树的中序序列push到队列q中 Node* head = q.front();//将队首节点（即所给树的最左节点）保存起来 q.pop(); head->_left = NULL;//将队首节点的左指针置空 Node* prev = head;//用prev保存当前节点 while(!q.empty())//当队列不空时进入循环 { Node* front = q.front();//获取队首节点 q.pop(); //将队首节点出队 prev->_right = front; //将前一个节点的右指针指向队首节点 front->_left = prev; //将队首节点的左指针指向上一个节点 front->_right = NULL; //将队首节点的右指针置空 prev = front; //更新保存上一个节点 } }