二叉搜索树
LC 98 & 99 & 面试题17.12BiNode
https://leetcode-cn.com/problems/validate-binary-search-tree/
https://www.jianshu.com/p/fa434a6a05ee
左中右的搜索顺序可以得到一个有序队列。
二叉搜索树的性质：
按照中序遍历，左中右，会得到一个有序数列。
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
即
- 当前节点的值是其左子树的值的上界（最大值）
- 当前节点的值是其右子树的值的下界（最小值）
方法1.因此，在遍历时可根据这个性质给出子树的范围，给出区间，判断值是否在这个区间里来判断是否是一个合适的。【但这个应该用 long long 因为给的数据中有最小值是INT_MIN】
方法2 .也可以存前一个值，然后和后面的比，这是https://www.jianshu.com/p/fa434a6a05ee 这里的方法。
但是和之前不同的是，这里学习一下引用的用法。
这里给一个res值，存前一个遍历的值，但是对于第一个值，res值无意义，这里又设置一个level值，当res值有意义时，level值会>0。
注意这里引用的运用。
lc98：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
执行用时：16 ms, 在所有 C++ 提交中击败了70.75%的用户
内存消耗：21 MB, 在所有 C++ 提交中击败了72.49%的用户
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isvalid(TreeNode*root,int &res,int &level){
if(root==NULL)
return true;
bool tmp = true;
tmp=tmp&&isvalid(root->left,res,level);
if(!tmp)
return tmp;
if(root->val<=res&&level!=0){
return false;
}
res = root->val;
level=level+1;
tmp=tmp&&isvalid(root->right,res,level);
return tmp;
}
bool isValidBST(TreeNode* root) {
//中序遍历是从小到大
if(!root)
return true;
int x = 0;
int level = 0;
return isvalid(root,x,level);
}
};
方法3.也可以得到整个数组，看合不合理。
lc99：
学习得到的思路：先遍历得到数组，然后得到数组中不合顺序的数字，再次遍历二叉树重置数字。
如果想用O(1)的空间，可学习一种新的遍历方法。莫里斯遍历。
参考链接：https://www.cnblogs.com/sunshuyi/p/12680577.html
这里使用传统的中序遍历左中右。
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recover-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
* 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 bianli(TreeNode* root,vector<int>& number){
if(root->left)
bianli(root->left,number);
number.push_back(root->val);
// cout<<root->val<<endl;
if(root->right)
bianli(root->right,number);
}
void bianli2(TreeNode* root,int x,int y){
// cout<<x<<y<<endl;
if(root->left)
bianli2(root->left,x,y);
if(root){
if(root->val==x){
root->val=y;
}else if(root->val==y){
root->val=x;
}
}
if(root->right)
bianli2(root->right,x,y);
}
void recoverTree(TreeNode* root) {
vector<int> number;
bianli(root,number);
int x=-1;
int y=-1;
int index=-1;
for(int i=0;i<number.size()-1;i++){
if(number[i]>number[i+1]){
// cout<<number[i]<<number[i+1]<<"sda"<<endl;
if(x==-1){
x=number[i];
index=i;
}else{
y=number[i+1];
}
}
}
if(y==-1)
y=number[index+1];
bianli2(root,x,y);
}
};
题解中精炼的写法。
class Solution{
public:
void inorder(TreeNode* root,vector<int>& nums){
if(root==nullptr){
return;
}
inorder(root->left,nums);
nums.push_back(root->val);
inorder(root->right,nums);
}
pair<int,int> findTwoSwapped(vector<int>& nums){
int n=nums.size();
int x=-1,y=-1;
for(int i=0;i<n-1;++i){
if(nums[i+1]<nums[i]){//17539 15379
y=nums[i+1];
if(x==-1){
x= nums[i];
}else
break;
}
}
return {x,y};
}
void recover(TreeNode* r,int count,int x,int y){//二次遍历其实是不是中序不重要。
if(r!=nullptr){
if(r->val==x||r->val==y){
r->val = r->val == x ? y : x;
if(--count==0)
return;
}
}
recover(r->left,count,x,y);
recover(r->right,count,x,y);
}
void recoverTree(TreeNode* root) {
vector<int> nums;
inorder(root, nums);
pair<int,int> swapped= findTwoSwapped(nums);
recover(root, 2, swapped.first, swapped.second);
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
时间复杂度：O(N)，其中 N 为二叉搜索树的节点数。中序遍历需要 O(N) 的时间，判断两个交换节点在最好的情况下是 O(1)，在最坏的情况下是 O(N)，因此总时间复杂度为 O(N)。
空间复杂度：O(N)。我们需要用 nums 数组存储树的中序遍历列表
面试题17.12BiNode
二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。
返回转换后的单向链表的头节点。
注意：本题相对原题稍作改动
示例：
输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
提示：
节点数量不会超过 100000。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binode-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
关键是转向，转向就要存前一个节点指针。
lc98也可以通过存前一个节点指针做到。
因为中序遍历是按照从小到大的顺序，这里就按照中序遍历存指针。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void isvalid(TreeNode*root,vector<TreeNode*> &res){
if(root==NULL)
return ;
isvalid(root->left,res);
if(res.size()>0){
res.back()->right=root;
}
root->left=NULL;
res.push_back(root);
isvalid(root->right,res);
return ;
}
TreeNode* convertBiNode(TreeNode* root) {
if(!root)
return root;
//先遍历得到，
// TreeNode* res;
vector<TreeNode*> res;
isvalid(root,res);
return res.front();
}
};
网友评论