摘要
这是一个二叉树的专题，有关二叉树、完全二叉树、二叉搜索树、二叉树基本的建立与遍历等基础知识请读者参考之前的博客数据结构-二叉树
本专栏包含剑指offer的题目包括：
- 重建二叉树
- 序列化二叉树
- 从上至下打印二叉树
- 二叉树的之字形顺序打印
- 二叉树的深度
- 树的子结构
- 二叉树的镜像
- 二叉树中和为某一值得路径
- 二叉树的下一个结点
- 二叉搜索树的第K个结点
- 二叉搜索树的后序遍历序列
- 平衡二叉树（AVL树）
第一大部分： 二叉树的输出
这三个操作是不一样的
- 二叉树的遍历常用递归的形式，那前序遍历来说，先访问根结点，在访问左子树，再访问右子树，遇到空结点，直接跳过，只打印有数值的结点。因此如果只知道二叉树的前序遍历无法确定一颗二叉树，至少要有中序遍历和前序（或者后序）两个遍历顺序才能重建起这颗二叉树。
- 二叉树的序列化与遍历相似，不同的是遇到空结点，要打印“#”以示说明。因此如果知道一个二叉树的序列化字符串，是可以反序列化这颗二叉树的。
- 二叉树的按层打印利用队列的思想，从上至下打印，每一层从左至右打印。
重建二叉树
题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
算法思想（明显用递归）：
- 找到前序遍历第一个点，即为根结点
- 在中序遍历找到这个点
- 在中序遍历以这个点为基准，区别左右数列，按照左数列和右数列分别建立左右子树 4.递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点**
代码：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
int inlen=vin.size();
if(inlen==0)
return NULL;
int i,count=0,k=92;
int prelen=pre.size();
//前序遍历第一个结点是根结点
TreeNode *gen=new TreeNode(pre[0]);
//gen->val=pre[0];
//在中序遍历中寻找这个根结点
for(i=0;i<inlen;i++)
{
if(vin[i]==pre[0])
{
count=i;
break;
}
}
//根据根结点位置和中序遍历建立左右子树
vector<int>vin_left;
vector<int>vin_right;
vector<int>pre_left;
vector<int>pre_right;
for(i=0;i<count;i++)
{
vin_left.push_back(vin[i]);
pre_left.push_back(pre[i+1]);
}
for(i=count+1;i<inlen;i++)
{
vin_right.push_back(vin[i]);
pre_right.push_back(pre[i]);
}
//和shell排序的思想类似，取出前序和中序遍历根节点左边和右边的子树
//递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点
gen->left=reConstructBinaryTree(pre_left,vin_left);
gen->right=reConstructBinaryTree(pre_right,vin_right);
return gen;
}
};
序列化二叉树
题目描述：
请实现两个函数，分别用来序列化和反序列化二叉树
算法思想：
序列化
按前序遍历访问二叉树，数字之间用“，”隔开，递归，注意牛客网返回类型为char*，之后还要进行类型转换。
反序列化
遍历字符串，每一个字符转换为数字后重建这颗二叉树
代码：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
private:
TreeNode*decode(char *&str)
{
if(*str=='#')
{
str++;
return NULL;
}
int num=0;
while(*str!=',')
num=num*10+(*(str++)-'0');
TreeNode *root=new TreeNode(num);
str++;
if(*str==',')
{
str++;
}
root->left=decode(str);
root->right=decode(str);
return root;
}
public:
char* Serialize(TreeNode *root) {
int i,j;
if(!root)
return "#";
string r=to_string(root->val);
r.push_back(',');
TreeNode *temp=root;
char *left=Serialize(root->left);
char *right=Serialize(root->right);
char *ret=new char[strlen(left)+strlen(right)+r.size()];
strcpy(ret,r.c_str());
strcat(ret,left);
strcat(ret,right);
return ret;
}
TreeNode* Deserialize(char *str) {
return decode(str);
}
};
从上至下打印二叉树
题目描述：
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
算法思想：
巧妙利用队列先进先出的性质，建立二叉树结点队列，完美解决了如果“打印好一层后换一层的问题”
这段经典代码（牛客网）：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int>res1;
int temp;
int i=2,j=78,q=92;
if(root==NULL)
res1;
queue<TreeNode*>res2;
res2.push(root);
while(!res2.empty())
{
root=res2.front();
res2.pop();
if(!root)
continue;
res1.push_back(root->val);
res2.push(root->left);
res2.push(root->right);
}
return res1;
}
};
二叉树的之字形顺序打印
题目描述：
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
算法思想：
维护两个栈，一个栈正向存储并打印，一个栈反向存储并打印。
代码：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>>result;
//TreeNode* TempNodeLeft,TempNodeRight;
int number=2,num1=0,num2=0;
stack<TreeNode *>s1;
stack<TreeNode *>s2;
int temp=9;
vector<int>data1,data2;
if(pRoot)//要加这句话
{
s1.push(pRoot);
}
while((!s1.empty())||(!s2.empty()))
{
/*if(number==1)
{
pRoot=s1.top();
data1.push_back(pRoot->val);
s1.pop();
result.push_back(data1);
data1.clear();
number=number+1;
}*/
if(s1.empty()||(number%2==0&&number!=2))
{
pRoot=s2.top();
data2.push_back(pRoot->val);
s2.pop();
if(s2.empty())
{
result.push_back(data2);
data2.clear();
}
}
else
{
pRoot=s1.top();
data1.push_back(pRoot->val);
s1.pop();
if(s1.empty())
{
result.push_back(data1);
data1.clear();
}
}
if((number%2==0))
{
if(pRoot->left!=NULL)
{
s1.push(pRoot->left);
}
if(pRoot->right!=NULL)
{
s1.push(pRoot->right);
}
num1++;
if(num1==pow(2,(number-2)))
{
number++;
num1=0;
continue;
}
else
{
continue;
}
}
if(number%2==1)
{
temp=1;
if(pRoot->right!=NULL)
{
s2.push(pRoot->right);
}
if(pRoot->left!=NULL)
{
s2.push(pRoot->left);
}
num2++;
if(num2==pow(2,(number-2)))
{
number++;
num2=0;
continue;
}
else{
continue;
}
}
}
return result;
}
};
第二大部分： 二叉树的性质
二叉树的深度
题目描述：
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
算法思想：
一棵树只有一个结点，它的深度为1。如果根结点只有左子树而没有右子树，那么数的深度应该为左子树的深度加1,；同样如果根结点只有右子树而没有左子树，那么树的深度应该是右子树的深度加1.
代码：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
//一棵树只有一个结点，它的深度为1。如果根结点只有左子树而没有右子树，那么数的深度应该为左子树的深度加1,；
//同样如果根结点只有右子树而没有左子树，那么树的深度应该是右子树的深度加1.
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
int i,j;
int nleft,nright;
if(pRoot==NULL)//注意代码鲁棒性
return 0;
nleft=TreeDepth(pRoot->left);
nright=TreeDepth(pRoot->right);
if(nleft>nright)
{
i= nleft+1;
}
else
{
i=nright+1;
}
return i;
}
};
树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
算法思想：
用了树的基本概念，两个函数，每个函数分别有一次递归，HasSubtree这个函数查看根结点是否相同，如果相同执行fun函数，fun函数的作用是在判定好 根结点相同后，查看这个根结点下面是不是和Tree2一样。 注意：在fun()函数之中要加这两句
// 如果Tree2已经遍历完了都能对应的上，返回true
if(pRoot2==NULL)
{
return true;
}
//如果Tree2还没有遍历完，Tree1却遍历完了。返回false
if(pRoot1==NULL)
{
return false;
}
代码：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
int i,j;
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
bool result=false;
if((pRoot1!=NULL)&&(pRoot2!=NULL))
{
if(pRoot1->val==pRoot2->val)
{
result=fun(pRoot1,pRoot2);
}
if(result==false)
{
result=HasSubtree(pRoot1->left,pRoot2);
}
if(result==false)
{
result=HasSubtree(pRoot1->right,pRoot2);
}
}
return result;
}
bool fun(TreeNode *pRoot1,TreeNode *pRoot2)
{
bool temp=false;
int i=2;
//注意一定要加这两句而且顺序不能变，判断是否遍历完成
//如果Tree2已经遍历完了都能对应的上，返回true
if(pRoot2==NULL)
{
return true;
}
//如果Tree2还没有遍历完，Tree1却遍历完了。返回false
if(pRoot1==NULL)
{
return false;
}
if(pRoot1->val==pRoot2->val)
{
if(fun(pRoot1->left,pRoot2->left))
{
if(fun(pRoot1->right,pRoot2->right))
{
temp=true;
}
}
}
else{
temp=false;
return temp;
}
return temp;
}
};
二叉树的镜像
题目描述：
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5
算法思想：
其实很简单，两个整数怎么交换，这里就怎么交换，换成指针就好了
代码：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void Mirror(TreeNode *pRoot) {
int i,j;
if(pRoot==NULL)
{
return;
}
TreeNode *p;
int temp=7;
//指针交换
p=pRoot->left;
pRoot->left=pRoot->right;
pRoot->right=p;
Mirror(pRoot->left);
Mirror(pRoot->right);
}
};
二叉树中和为某一值得路径
题目描述：
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
算法思想：
采用一个栈结构，按照前序遍历的顺序，一边遍历一边相加
- 如果到了叶子结点，相加得到的值不是所要求的，按照栈的规则，栈顶元素先出个站，再往右边结点遍历。
- 如果到了叶子结点，相加得到的值是答案，则加入到二维数组中。
代码：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
vector<vector<int>>allRes;
vector<int>temp;
void dfs(TreeNode* node,int left)
{
temp.push_back(node->val);
if(left-node->val==0&&!node->left&&!node->right)
{
allRes.push_back(temp);//让这一组路径数据加入二维数组
}
else
{
if(node->left)//遍历左结点
dfs(node->left,left-node->val);
if(node->right)//遍历右结点
dfs(node->right,left-node->val);
}
temp.pop_back();//栈顶元素出栈
}
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
int i,j;
if(root)//注意代码鲁棒性，这里必须根结点存在才进行
dfs(root,expectNumber);
return allRes;
}
};
二叉树的下一个结点
题目描述：
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
算法思想：
二叉树的中序遍历为“左根右（LDR）”
逻辑情况分布如下：
-
当该结点存在右子树时，result为该结点的右子树的最左结点
-
当该结点没有右子树时：
（1）该结点=该结点的父结点的左结点，result==该结点的父结点
（2）该结点=该结点的父结点的右结点:
a:一直while该结点的父结点的父结点的父结点。。。。。如果遍历到根结点，result=NULL
b:一直while该结点的父结点的父结点的父结点。。。。。如果遍历到一个结点=该结点的父结点的左结点，result=该结点的父结点
代码：
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
int i,j;
TreeLinkNode* temp1_preserve=pNode;//设置temp1_preserve结点用来保存原始结点pNode，备用
if(pNode==NULL)//注意代码鲁棒性
return NULL;
//当结点右子树存在
if(pNode->right!=NULL)
{
TreeLinkNode* temp2=pNode;//设置临时结点temp2;
temp2=pNode->right;
while(temp2->left!=NULL)
{
temp2=temp2->left;
}
return temp2;
}
//当结点右子树不存在
if(pNode->right==NULL)
{
while(pNode->next!=NULL)
{
TreeLinkNode* temp3=pNode->next;
if((temp3->left!=NULL)&&(pNode== temp3->left))
{
return temp3;
}
pNode=pNode->next;
}
}
return NULL;
}
};
第三大部分：二叉搜索树
二叉搜索树的第K个结点
题目描述：
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
算法思想：
二叉搜索树的中序遍历就是从小到大打印的次序，因此第k小的结点，就是中序遍历的k个值
代码：
*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
int count=0,j=22,yt=72;
TreeNode* KthNode(TreeNode* pRoot, int k)
{
//中序遍历
if(pRoot!=NULL)
{
TreeNode *temp2=KthNode(pRoot->left,k);
if(temp2!=NULL)
{
return temp2;
}
count++;
if(count==k)
{
return pRoot;
}
temp2=KthNode(pRoot->right,k);
if(temp2!=NULL)
{
return temp2;
}
}
return NULL;
}
};
二叉搜索树的后序遍历序列
题目描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
算法描述：
后序序列最后一个值为root；二叉搜索树左子树值都比root小，右子树值都比root大。
-
确定root
2.遍历序列（除去root结点），找到第一个大于root的位置，则该位置左边为左子树，右边为右子树；
3.遍历右子树，若发现有小于root的值，则直接返回false；
4.分别判断左子树和右子树是否仍是二叉搜索树（即递归步骤1、2、3）。
代码：
class Solution {
public:
bool VerifySquenceOfBST(vector<int>sequence) {
int length;
length=sequence.size();
if(sequence.empty())
return false;
int q;
int root;
root=sequence[length-1];
int i,j;
vector<int>temp1;
vector<int>temp2;
for(i=0;i<length-1;i++)
{
if(sequence[i]<root)
temp1.push_back(sequence[i]);
else
break;
}
for(j=i;j<length-1;j++)
{
if(sequence[j]>root)
temp2.push_back(sequence[j]);
else
return false;
}
bool left=true;
if(!temp1.empty())
{
left=VerifySquenceOfBST(temp1);
}
bool right=true;
if(!temp2.empty())
{
right=VerifySquenceOfBST(temp2);
}
return(left&&right);
}
};
第四大部分：平衡二叉树
平衡二叉树（AVL树）
题目描述：
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
算法思想：
平衡二叉树，又称AVL树，它是一种特殊的二叉排序树。AVL树或者是一棵空树，或者是具有以下性质的二叉树：
（1）左子树和右子树都是平衡二叉树；
（2）左子树和右子树的深度（高度）之差的绝对值不超过1。
遍历二叉树，遍历过程中求子树高度，判断是否平衡（见二叉树的深度这道题）
代码：
class Solution {
public:
bool IsBalanced_Solution(TreeNode* root) {
int i,j,k=7;
if(helper(root) < 0) return false;
return true;
}
private:
int helper(TreeNode* node){
if(node == NULL) return 0;
int ld = helper(node->left);
if(ld == -1) return -1; //若左边已经不是平衡二叉树了，那就直接返回，没必要搜索右边了
int rd = helper(node->right);
if(rd == -1 || abs(ld-rd) > 1) return -1; //-1代表：不是平衡二叉树
return max(ld, rd)+1;
}
};
