做二叉树已经有两天的时间了，这两天在牛客上把剑指offer中和牛客考/保研机试中的树的题都做了。emmm，感受颇深。下面开始正题。
树的本质就是递归！递归！递归！
目录
一、树的结构，给出leetcode常用的标准板子；
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
}; 二、遍历方法
二叉树最重要的就是四种遍历方法，只要掌握了这四种遍历方法，剩下就是套题的过程了。
1.前序遍历
void preOrder(TreeNode *Head)
{
if(Head==NULL)
return ;
visit(Head);
preOrder(Head->leftChild);
preOrder(Head->rightChild);
return ;
}; 2.中序遍历
void inOrder(TreeNode *Head)
{
if(Head==NULL)
return ;
inOrder(Head->leftChild);
visit(Head);
inOrder(Head->rightChild);
return ;
}; 3.后序遍历
void postOrder(TreeNode *Head)
{
if(Head==NULL)
return ;
postOrder(Head->leftChild);
postOrder(Head->rightChild);
visit(Head);
return ;
}; 4.层次遍历
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> vec;
queue<TreeNode*>q;
if(root==NULL)
return vec;
q.push(root);
while(!q.empty())
{
TreeNode *r=q.front();
vec.push_back(r->val);
q.pop();
if(r->left!=NULL)
q.push(r->left);
if(r->right!=NULL)
q.push(r->right);
}
return vec;
} 三、相关题目（以剑指offer为准）
从热度高到低排列
1.二叉树的镜像
解题思路：从图中的描述可知，此题就是将二叉树的左右两棵子树进行交换。只要使用前序遍历就可以完成。
交换过程共分四种情况：父节点不存在；父节点两棵子树都存在；父节点两棵子树只存在一棵；父节点无子树。
代码如下：
void Mirror(TreeNode *pRoot) {
if(pRoot==NULL)
return;
if(pRoot->left!=NULL && pRoot->right!=NULL)
{
TreeNode *temp=pRoot->left;
pRoot->left=pRoot->right;
pRoot->right=temp;
}
else if(pRoot->left!=NULL && pRoot->right==NULL)
{
pRoot->right=pRoot->left;
pRoot->left=NULL;
}
else if(pRoot->left==NULL && pRoot->right!=NULL)
{
pRoot->left=pRoot->right;
pRoot->right=NULL;
}
else
return ;
Mirror(pRoot->left);
Mirror(pRoot->right);
} 2.树的子结构
注：这里的子结构可能大家会有一个歧义，认为其实就是判断B是不是A的子树。其实不然。
如下图，即使树2不是树1的子树，但是树1中仍然包含树2，所以树2也是树1的子结构。
解题思路：通过对子结构的认识，相信大家也很快知道了这个题就是判断B包不包含在A中。如果抛弃树的概念，给定大家一个字符串A和一个字符串B，问A中包不包含B，相信很快有同学想到要用str.find(string s)这个函数。如果我们认真分析一下。我们要将A和B进行匹配。一种简单的办法(KMP除外)就是先找到B[0]在A中的位置，如果B[0]匹配了，就去匹配B[1],B[2]...，如果不成功，返回到第一个B[0]匹配的位置的下一个位置，继续寻找匹配，如果匹配成功，就返回true；
这是在字符串进行匹配。那么换成树呢？
依旧是这样的，我们先找到第一个匹配的节点。然后匹配成功，就继续递归子树，匹配子树。如果失败就继续寻找匹配。
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
bool result=false;
if(pRoot1!=NULL && pRoot2!=NULL) //只要有一个树为空就返回false
{
if(pRoot1->val==pRoot2->val)
{
result=doesTree1hasTree2(pRoot1,pRoot2);
}
if(!result)
result=HasSubtree(pRoot1->left,pRoot2);
if(!result)
result=HasSubtree(pRoot1->right,pRoot2);
}
return result;
}
bool doesTree1hasTree2(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot2==NULL) //如果pRoot2遍历完了，返回true
return true;
if(pRoot1==NULL) //如果pRoot2还没遍历完但是pRoot1遍历完了，返回false
return false;
if(pRoot1->val!=pRoot2->val)
return false;
//如果相等的话，继续遍历对应的左子树和右子树
return doesTree1hasTree2(pRoot1->left,pRoot2->left)&& doesTree1hasTree2(pRoot1->right,pRoot2->right);
} 3.从上往下打印二叉树
解题思路：层次遍历；代码在前边给出了。
3.1 相似题目1
解题思路：这个题相较于上一题多了一个要求，就是要在每一层输出一行换行。
所以我们要用队列的特性记录每一层的节点。
代码如下：
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> v;
vector<int> vec;
queue<TreeNode *> q;
if(pRoot==NULL)
return v;
q.push(pRoot);
int cur,len;
while(!q.empty())
{
cur=0; //记录分层
len=q.size(); //记录分层
while(cur++<len)
{
TreeNode* root=q.front();
q.pop();
vec.push_back(root->val);
if(root->left!=NULL)
q.push(root->left);
if(root->right!=NULL)
q.push(root->right);
}
v.push_back(vec);
vec.clear();
}
return v;
} 3.2 相似题目2 （按之字形顺序打印二叉树）
解题思路：这个题相对于3.1的变种来说，又多了一个要求，那就是按照之字形打印。当然细心的同学也能很快发现一个规律：层数是奇数的从左向右打印。层数是偶数的从右往左打印。所以换汤不换药。只要输出的时候判断一下就好了。代码如下：
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> v,tempv; //最后的返回值
vector<int> vec; //临时存放每一层节点的值
queue<TreeNode *> q; //队列
int pos,len;
if(pRoot==NULL)
return v;
q.push(pRoot);
while(!q.empty())
{
pos=0;
len=q.size(); //每一层的节点数量
while(pos++<len)
{
TreeNode *root=q.front();
q.pop();
vec.push_back(root->val);
if(root->left!=NULL)
q.push(root->left);
if(root->right!=NULL)
q.push(root->right);
}
v.push_back(vec);
vec.clear();
}
for(int i=0;i<v.size();i++)
{
if((i+1)%2==1)//(i+1)为奇数，从左到右输出；为偶数，从右到左输出
tempv.push_back(v[i]);
else //如果是偶数就逆序输出
{
vec.clear();
for(int j=v[i].size()-1;j>=0;j--)
{
vec.push_back(v[i][j]);
}
tempv.push_back(vec);
}
}
return tempv;
} 4.二叉搜索树的后序遍历序列
解题思路：这个题大家可能楞的一看，完全没有思路。。。。但是我们可以把抽象问题具体化。画图写后序遍历来试一试。我写递归的原则就是我要先懂，然后计算机才能懂。
注意：这里边不是二叉树，而是 二叉搜索树。二叉搜索树是一种特殊的二叉树。树的左孩子都<=他，树的右孩子都>=他。
通过上图可以看到，后序遍历的最后一个节点就是树的根节点。而我们又知道，二叉搜索树的左子树都<=他，右子树都>=他，所以我们可以发现一个规律， 在后序遍历中5的后边是7，也就是根节点的右子树，都>5,接下来就是3，也就到了左子树部分。而2.3.4都是小于5的。那么这样我们这个题就有解了：
我们可以先把后序reverse反序一下。然后第一个节点就是根节点，紧接着我们找根节点后的第一个小于根节点的位置index。为什么？
因为这个节点把树分成了两部分，一部分比树根大，一部分比树根小。so，，如果我们在index后发现了比树根大的，那么很显然这不成立。然后我们继续递归下去。就会发现答案。
bool VerifySquenceOfBST(vector<int> sequence) {
//后续遍历的最后一个节点是根节点，可以把搜索树分成两部分
//找到第一个比根节点小的集和，因此划成左右子树，左集合里不能有比根节点大的。如果有return false
//算法流程：
//判断vector是否为空，不为空，继续判断，若为空 return false
//拿出右边第一个元素(根节点)c
//从右往左找到第一个比根节点小的节点下标index
//划分集和，把(0,index)划分为一组，判断这组里是否有比根节点c大的，如果有return false
//如果没有，继续划分，直到找不到比c小的，return true；
if(sequence.size()==0)
return false;
int c=sequence[sequence.size()-1]; //根节点
int index; //找到第一个比c根节点小的节点
for(index=sequence.size()-2;index>=0;index--)
{
if(sequence[index]<c)
break;
}
if(index<0) //没有找到比c小的节点，return true；
return true;
vector<int> temp;
for(int i=0;i<=index;i++)
{
if(sequence[i]>c)
return false;
temp.push_back(sequence[i]);
}
return VerifySquenceOfBST(temp);
} 5.二叉树中和为某一值的路径
解题思路：
未完待续。。。。持续更新
京公网安备 11010502036488号