剑指offer_牛客_二叉树合集1
二叉树相关概念
- 二叉树：是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。
- 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
|----------| | 1 | | / \ |---度数为2 | 2 3 | |----------| | /\ /\ | |4 5 6 7 |---度数为0 |----------| - 完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。
1 / \ 2 3 /\ 4 5 - 二叉查找树：它或者是一棵空树，或者是具有下列性质的二叉树 (若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。)
二叉树相关试题
1. JZ4—重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
示例1
输入
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值
{1,2,5,3,4,6,7}
思路
DFS
题解
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.size()==0) return nullptr;
TreeNode* root = new TreeNode(pre[0]);
if(pre.size()==1) return root;
int r = 0;
for(int i=0;i<vin.size();i++){
if(vin[i] == pre[0]){
r = i;
}
}
vector<int> prel = vector<int>(pre.begin()+1,pre.begin()+r+1);
vector<int> prer = vector<int>(pre.begin()+r+1,pre.end());
vector<int> vinl = vector<int>(vin.begin(),vin.begin()+r);
vector<int> vinr = vector<int>(vin.begin()+r+1,vin.end());
root->left = reConstructBinaryTree(prel, vinl);
root->right = reConstructBinaryTree(prer, vinr);
return root;
}
};
2. JZ17-树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
示例1
输入
{8,8,#,9,#,2,#,5},{8,9,#,2}
返回值
true
思路
因为空树不是任何树的子结构，所以空树也不可能为任何树的父结构。
所以第一步就是，如果两棵树任意一颗为空，返回false。
然后就是递归判断，先判断B是不是A的同根子结构，不是再判断B是不是A左子树或右子树的同根子结构。以此类推，直到找到A的某颗子树是B的同根子结构返回true;或者A所有的子树都遍历完返回false。
题解
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if (pRoot1 == nullptr || pRoot2 == nullptr) return false;
return HasSameRootSubtree(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
}
bool HasSameRootSubtree(TreeNode *pRoot1, TreeNode *pRoot2) {
if (pRoot2 == nullptr) return true;
if (pRoot1 == nullptr || pRoot1->val != pRoot2->val) return false;
return HasSameRootSubtree(pRoot1->left, pRoot2->left) && HasSameRootSubtree(pRoot1->right, pRoot2->right);
}
};
3. JZ18-二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
比如： 源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
示例1
输入
{8,6,10,5,7,9,11}
返回值
{8,10,6,11,9,7,5}
思路
通过递归的方法，让树从叶子结点的父结点开始交换即可。需要考虑该父节点一个左叶子、一个右叶子、两个叶子三种情况。
题解
class Solution {
public:
TreeNode* Mirror(TreeNode* pRoot) {
if(pRoot != nullptr) parseLR(pRoot);
return pRoot;
}
pair<TreeNode*, TreeNode*> TranLR(TreeNode* l, TreeNode* r) {
if(l == nullptr && r != nullptr && r->left == nullptr && r->right == nullptr) return pair<TreeNode*, TreeNode*>(r, l);
if(r == nullptr && l != nullptr && l->left == nullptr && l->right == nullptr) return pair<TreeNode*, TreeNode*>(r, l);
if(l != nullptr && r != nullptr && r->left == nullptr && r->right == nullptr && l->left == nullptr && l->right == nullptr) return pair<TreeNode*, TreeNode*>(r, l);
if(l != nullptr) parseLR(l);
if(r != nullptr) parseLR(r);
return pair<TreeNode*, TreeNode*>(r, l);
}
void parseLR(TreeNode* r) {
pair<TreeNode*, TreeNode*> rc = TranLR(r->left, r->right);
r->left = rc.first;
r->right = rc.second;
}
};
4. JZ22-从上往下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
示例1
输入
{5,4,#,3,#,2,#,1}
返回值
[5,4,3,2,1]
思路
BFS
题解
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> ans;
vector<TreeNode*> tree;
ans.clear();
if(root == nullptr) return ans;
tree.push_back(root);
for(int i=0;i<tree.size();i++){
ans.push_back(tree[i]->val);
if(tree[i]->left) tree.push_back(tree[i]->left);
if(tree[i]->right) tree.push_back(tree[i]->right);
}
return ans;
}
};
5. JZ23-二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）
示例1
输入
[4,8,6,12,16,14,10]
返回值
true
思路
后序遍历是左子树、右子树、根，所以数组最后一个是跟。然后按二叉搜索树的规律比根小的是左子树，比根大的是右子树。根据后序遍历的规律，左子树一定在右子树左边。根据这些条件就可以递归完成判断。如果不约定空树不是二叉搜素树，代码还可以更简洁点。
题解
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.empty()) return false;
if(sequence.size() == 1) return true;
int root = sequence.back();
vector<int> l,r;
for(int i=0;i<sequence.size()-1;i++){
if(sequence[i]<root){
l.push_back(sequence[i]);
if(!r.empty()) return false;
}
if(sequence[i]>root){
r.push_back(sequence[i]);
}
}
return (l.empty() || VerifySquenceOfBST(l)) && (r.empty() || VerifySquenceOfBST(r));
}
};
6. JZ24-二叉树中和为某一值的路径
输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
示例1
输入
{10,5,12,4,7},22
返回值
[[10,5,7],[10,12]]
思路
DFS
题解
class Solution {
private:
vector<vector<int> > ans;
public:
void Search(TreeNode* root, vector<int> temp, int expectNumber) {
if(root == nullptr) return ;
temp.push_back(root->val);
if(root->left == nullptr && root->right == nullptr){
int sum = 0;
for(int i=0;i<temp.size();i++){
sum += temp[i];
}
if(sum == expectNumber)
this->ans.push_back(temp);
}
if(root->left != nullptr) Search(root->left, temp, expectNumber);
if(root->right != nullptr) Search(root->right, temp, expectNumber);
temp.pop_back();
}
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<int> temp;
Search(root, temp, expectNumber);
return this->ans;
}
};
