leetcode 95. 不同的二叉搜索树
- 此题使用动态规划的方式
- 任何二叉搜索树的形式都是
左子树的个数*右子树的个数 - 所以对于任何大小为n的二叉树，总的种类有左子树从0到n-1同时右子树大小从n-1到0，每次计算左子树种类*右子树种类，再求和
class Solution {
public:
int numTrees(int n) {
vector<int> arr(n+1, 0);
arr[0] = 1;
arr[1] = 1;
for(int i = 2; i<=n; ++i)
{
for(int j = 0; j<i; ++j)
{
arr[i]+=arr[j]*arr[i-j-1];
}
// cout<<arr[i]<<ends;
}
return arr[n];
}
};leetcode 331.验证二叉树的前序序列化
- 此题采用使用栈模拟递归的方式实现验证，初始时刻先把一个根节点push到栈中，每次先在字符串里寻找结尾或者是逗号，假如找到了说明当前元素结束了，那么回看上一个位置的当前元素（因为现在不是在字符串结尾就是在逗号上），假如是
#就说明上一个位置没有元素，那么直接弹出栈中的一个元素（认为是NULL节点），假如不是说明上一个位置是个节点，那么栈中弹出该元素的同时压入两个元素（该元素的左右孩子）class Solution {
public:
bool isValidSerialization(string preorder) {
if(preorder[0] == '#')
{
if(preorder.size()>1)return false;
else return true;
}
queue<int> q;
q.push(0);
int index = 0;
while(index<preorder.size())
{
while(index<preorder.size()&&preorder[index]!=',')index++;
char temp = preorder[index-1];
if(temp!='#')
{
if(q.size())
{
q.pop();
q.push(0);
q.push(0);
}
else return false;
}
else
{
if(q.size())
{
q.pop();
}
else return false;
}
index++;
}
if(q.size())return false;
else return true;
}
};对称二叉树
- 使用递归方式，左侧的左孩子和右侧的右孩子，与左侧的右孩子和右侧的左孩子是否相等，实现递归
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root)return comp(root->left, root->right);
else return true;
}
bool comp(TreeNode* left, TreeNode* right)
{
if(left&&right)
{
if(left->val != right->val)return false;
}
else if(left||right)return false;
else if(!left && !right)return true;
return comp(left->left, right->right)&&comp(left->right, right->left);
}
};leetcode 114.二叉树展开为链表
- 将左子树插入到右子树的地方
- 将原来的右子树接到左子树的最右边节点
- 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null
- 实际上就是在遍历的过程中先遍历自己，然后左子树，与前序相同，然后左子树完全结束之后才到右子树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
if(!root||(root->left == NULL && root->right == NULL))return;
TreeNode* temp = root;
while(temp)
{
TreeNode* tRight = temp->right;
TreeNode* tempL = temp->left;
if(tempL)
{
while(tempL->right)
{
tempL = tempL->right;
}
tempL->right = temp->right;
temp->right = temp->left;
}
else
{}
temp->left = NULL;
temp = temp->right;
}
}
};
Leetcode 669.修剪二叉搜索树
- 如果当前节点太小，则递归返回自己的右侧子树
- 如果太大则返回左侧的子树
- 如果满足，则递归修剪自己的左右子树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(!root)return NULL;
if(root->val<low)
{
return trimBST(root->right, low, high);
}
else if(root->val>high)
{
return trimBST(root->left, low, high);
}
else
{
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
}
return root;
}
};
Leetcode 106. 从中序与后序遍历序列构造二叉树
- 首先找出后序遍历的最后一个节点为当前节点
- 用这个节点分割中序遍历的数列为左右两部分
- 假设中序左半部分的大小为s1，右半部分为s2（二者均不包括当前节点）
- 利用二者的尺寸划分后续遍历的数组，后续遍历的前s1个就是左半部分，第s1+1到s1+s2个是右半部分，不包括最后一个元素也就是当前节点
class Solution {
private:
// 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
if (postorderBegin == postorderEnd) return NULL;
int rootValue = postorder[postorderEnd - 1];
TreeNode* root = new TreeNode(rootValue);
if (postorderEnd - postorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割后序数组
// 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
int leftPostorderBegin = postorderBegin;
int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
// 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
// 左闭右开的原则
return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}
};
Leetcode 105. 从前序与中序遍历序列构造二叉树
- 原理相同，利用前序遍历划分中序数组
- 中序数组的左半边是左子树，右半边是右子树
- 根据这两个树的大小反过来将前序数组划分为两部分
class Solution {
private:
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {
if (preorderBegin == preorderEnd) return NULL;
int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0
TreeNode* root = new TreeNode(rootValue);
if (preorderEnd - preorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割前序数组
// 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
int leftPreorderBegin = preorderBegin + 1;
int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size
// 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
int rightPreorderEnd = preorderEnd;
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, preorder, leftPreorderBegin, leftPreorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (inorder.size() == 0 || preorder.size() == 0) return NULL;
// 参数坚持左闭右开的原则
return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());
}
};
Leetcode 450. 删除二叉搜索树中的节点
- 如果当前节点只有左/右孩子，那就将当前节点改为其左/右孩子
- 如果双侧孩子都在，则将自己的左孩子移动到右孩子所在子树上的最左空节点，然后修改当前节点为右孩子
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root)return NULL;
if(root->val>key)
{
root->left = deleteNode(root->left, key);
return root;
}
else if(root->val<key)
{
root->right = deleteNode(root->right, key);
return root;
}
else
{
if(!root->left && !root->right)
{
return NULL;
}
else if(root->left && !root->right)
{
return root->left;
}
else if(!root->left && root->right)
{
return root->right;
}
else
{
// cout<<root->left->val<<endl;
TreeNode* right = root->right;
TreeNode* temp = root->right;
while(temp->left)
{
temp = temp->left;
}
temp->left = root->left;
return right;
}
}
}
};
Leetcode 538. 把二叉搜索树转换为累加树
- 此题是每个节点的值保存为比这个节点大的节点值之和
- 此时只需要更换中序遍历的顺序，改为右-中-左，就可以实现由大到小的遍历，顺手累加即可
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
TreeNode* temp, * node;
stack<TreeNode*>s;
int sum = 0;
if(!root)return NULL;
s.push(root);
while(s.size())
{
temp = s.top();
s.pop();
if(temp)
{
if(temp->left)s.push(temp->left);
s.push(temp);
s.push(NULL);
if(temp->right)s.push(temp->right);
}
else
{
node = s.top();
s.pop();
int temp = node->val;
node->val+=sum;
sum+=temp;
// arr.push_back(node);
}
}
return root;
}
};
kama网 51. 平移二叉树（第七期模拟笔试）
- 此题主要是先将二叉树按层读取并且存储起来，然后从下而上每层向前位移，然后将上一层和下一层的父子结点连接起来然后继续向前平移上一层循环往复
- 注意可以通过
if(cin>>ch)的形式判断cin是否遇到了EOF
using namespace std;
struct TreeNode
{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int i):val(i), left(NULL), right(NULL){}
};
void movek(int k, vector<TreeNode*>& arr)
{
for(int i = 0; i<k; ++i)
{
TreeNode* tmp = arr[0];
TreeNode* cur = arr[1];
for(int j = 0; j<arr.size(); ++j)
{
cur = arr[(j+1)%arr.size()];
arr[(j+1)%arr.size()] = tmp;
tmp = cur;
}
}
}
int main()
{
int k, n;
cin>>k>>n;
vector<vector<TreeNode*>> tree;
queue<TreeNode*> q;
int tmp;
cin>>tmp;
TreeNode* node;
node = new TreeNode(tmp);
q.push(node);
tree.push_back({node});
bool flag = true;
for(int i = 0; flag && i<n-1; )
{
tree.push_back({});
int s = q.size();
TreeNode* temp;
for(int j = 0; j<s; ++j)
{
temp = q.front();
q.pop();
if(temp->val == -1)continue;
if(cin>>tmp)++i;
else {flag = false;break;};
temp = new TreeNode(tmp);
q.push(temp);
tree[tree.size()-1].push_back(temp);
if(cin>>tmp)++i;
else {flag = false;break;}
temp = new TreeNode(tmp);
q.push(temp);
tree[tree.size()-1].push_back(temp);
}
}
for(int i = tree.size()-1; i>0; --i)
{
movek(k, tree[i]);
int m = 0;
for(int j = 0; j<tree[i-1].size(); ++j)
{
if(tree[i-1][j]->val == -1)continue;
tree[i-1][j]->left = tree[i][m];
++m;
tree[i-1][j]->right = tree[i][m];
++m;
}
}
queue<TreeNode*> q1;
q1.push(tree[0][0]);
TreeNode* top;
while(q1.size())
{
top = q1.front();
q1.pop();
cout<<top->val<<' ';
if(top->left)q1.push(top->left);
if(top->right)q1.push(top->right);
}
}