《剑指Offer》树考点题解
2020-03-24 本文已影响0人
风之旅人c
题目链接：把二叉树打印成多行
题目简述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
题解思路
分层打印二叉树，可以预见到，利用BFS搜索的思想即可做到。
题解代码
/*
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> > vv;
queue<TreeNode*> qu;
vector<int> v;
if(pRoot == NULL) return vv;
qu.push(pRoot);
while(!qu.empty())
{
int qs = qu.size();
while(qs--)
{
v.push_back(qu.front()->val);
if(qu.front()->left != NULL) qu.push(qu.front()->left);
if(qu.front()->right != NULL) qu.push(qu.front()->right);
qu.pop();
}
vv.push_back(v);
v.clear();
}
return vv;
}
};
题目链接：按照之字形打印二叉树
题目简述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
题解思路
与上一题类似，但是多了一个在奇数行(假设第一行是第零行）反向打印，设置一个标记flag即可。
题解代码
/*
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> > vv;
queue<TreeNode*> qu;
vector<int> v;
int f = 0;
if(pRoot == NULL) return vv;
qu.push(pRoot);
while(!qu.empty())
{
int qs = qu.size();
while(qs--)
{
v.push_back(qu.front()->val);
if(qu.front()->left != NULL) qu.push(qu.front()->left);
if(qu.front()->right != NULL) qu.push(qu.front()->right);
qu.pop();
}
f++;
if(f%2 == 0)
{
reverse(v.begin(), v.end());
}
vv.push_back(v);
v.clear();
}
return vv;
}
};
题目链接：重建二叉树
题目简述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
题解思路
做这道题目，前序遍历和中序遍历的关系一定要清楚，前序遍历的第一个点一定是根节点，然后我们在中序遍历找到根节点，则中序遍历前面是左子树，后面是右子树，然后递归地进行下去。
题解代码
/**
* 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) {
if(pre.size() == 0 || vin.size() == 0) return NULL;
TreeNode* root = new TreeNode(pre[0]);
for(int i=0; i<vin.size(); ++i)
{
if(vin[i] == pre[0])
{
vector<int> a;
vector<int> b;
a.assign(pre.begin()+1, pre.begin()+i+1);
b.assign(vin.begin(), vin.begin()+i);
root->left = reConstructBinaryTree(a, b);
a.clear();
b.clear();
a.assign(pre.begin()+i+1, pre.end());
b.assign(vin.begin()+i+1, vin.end());
root->right = reConstructBinaryTree(a, b);
}
}
return root;
}
};
题目链接：二叉树的下一个结点
题目简述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
题解思路
给定的是中序遍历，我们拿到了当前节点，想要找到下一个节点，这样有两个情况。如果我们有右子树，那么下一个节点一定在右子树中：进入右子树，我们重新中序遍历，下一个点一定是最左的叶子节点。另一种情况是没有右子树，那么下一个节点一定是他的父亲节点以上，如果当前节点是父亲节点的右节点，那么要继续向上搜索，如果是左节点，那就是该节点。
题解代码
/*
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)
{
if(pNode == NULL) return NULL;
if(pNode->right != NULL)
{
pNode = pNode->right;
while(pNode->left != NULL) pNode = pNode->left;
return pNode;
}
while(pNode->next != NULL)
{
if(pNode->next->left == pNode)
return pNode->next;
pNode = pNode->next;
}
return NULL;
}
};
题目链接：对称的二叉树
题目简述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
题解思路
这道题其实很简单，当初做的时候只是搞错了这个镜像的定义，这个镜像只是针对整个二叉树而言的，对于子树没有要求。
题解代码
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool judge(TreeNode* node1, TreeNode* node2)
{
if(node1 == NULL && node2 == NULL) return true;
if(node1 == NULL || node2 == NULL) return false;
if(node1->val == node2->val)
{
return judge(node1->left, node2->right) && judge(node1->right, node2->left);
}
return false;
}
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot == NULL) return true;
return judge(pRoot->left, pRoot->right);
}
};
