本文将为您提供关于99.RecoverBinarySearchTree的详细介绍，同时，我们还将为您提供关于108.ConvertSortedArraytoBinarySearchTree、1099B
本文将为您提供关于99. Recover Binary Search Tree的详细介绍，同时，我们还将为您提供关于108. Convert Sorted Array to Binary Search Tree、1099 Build A Binary Search Tree、1099 Build A Binary Search Tree (30)、1099 Build A Binary Search Tree （30 分）的实用信息。
本文目录一览：- 99. Recover Binary Search Tree
- 108. Convert Sorted Array to Binary Search Tree
- 1099 Build A Binary Search Tree
- 1099 Build A Binary Search Tree (30)
- 1099 Build A Binary Search Tree （30 分）
99. Recover Binary Search Tree
原题链接
Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
解题的关键是找到两个错误的节点。由于是二分搜索树，可以比较节点与其父节点或子节点的大小关系，来判断是否有问题。可是，即使找到了某个节点与其子节点的大小关系不符合BST的要求，还要进一步确认到底是该节点有问题还是子节点有问题，就比较麻烦了。所以从树结构中去找是比较麻烦的。BST有一个特性，就是用中序遍历输出节点的话，是一个递增的序列，所以我们可以把树“线性化”再来观察。假如一个BST用中序遍历输出123456，交换3、5节点变成125436，可以观察到，必然形成的局面是，第一个出现的交换节点一定比它的后一个节点大，第二个出现的交换节点一定比它的前一个节点小。
因此，我们可以在中序遍历时用一个变量跟踪前一个输出的节点，当第一次出现前一个节点比当前节点大的情况时，前一个节点就是交换节点；当第二次出现这种情况时，当前节点是交换节点。问题是，一般的中序遍历是递归实现，空间复杂度最坏是O(n)，最好也要O(lgn)，不符合题目O(1)的要求。我从网上找了下，要实现O(1)的中序遍历只能用Morris Traversal，其实就是线索二叉树的方法。
中序遍历之所以常用递归，是因为遍历完左子树后要回溯到根节点。当一个节点有左子树时，中序遍历输出时它的前一个节点（即前驱节点）是左子树的“最右节点”，通俗点讲就是“右下角”。由于右下角的右子树一定是空的（不然它就不是右下角了），所以可以把它的右指针指向根节点，这样在遍历时就可以回溯到根节点了。为了不改变树的结构，回到根节点后，还要在找到这个右下角，把它的右指针重新赋为空。
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode* prev = NULL;
TreeNode* tmp = NULL;
TreeNode* first = NULL;
TreeNode* second = NULL;
while(root!=NULL) {
if(root->left!=NULL) {
tmp = root->left;
while(tmp->right!=NULL && tmp->right!=root) tmp = tmp->right;
if(tmp->right==NULL) {
tmp->right = root;
root = root->left;
}
else {
tmp->right = NULL;
//find wrong elements
if(first==NULL && prev->val>root->val) first = prev;
if(first!=NULL && prev->val>root->val) second = root;
prev = root;
//end finding
root = root->right;
}
}
else {
//find wrong elements
if(first==NULL && prev!=NULL && prev->val>root->val) first = prev;
if(first!=NULL && prev->val>root->val) second = root;
prev = root;
//end finding
root = root->right;
}
}
//swap
int temp = first->val;
first->val = second->val;
second->val = temp;
}
};
代码中，first、second记录两个交换的节点，prev跟踪前一个遍历的节点。如果当前节点有左子树，在开始左子树遍历前，都要先找到它的前驱节点。如果前驱节点的右指针已经指向当前节点了，说明左子树已经遍历完了，可以处理当前节点并遍历右子树。因为中序遍历是按“左中右”的顺序，所以改变前驱节点的右指针也是符合遍历习惯的。
108. Convert Sorted Array to Binary Search Tree
1 class Solution { 2 public TreeNode sortedArrayToBST(int[] nums) { 3 int size = nums.length; 4 return helper(nums,size - 1); 5 6 } 7 8 public TreeNode helper(int[] nums,int lo,int hi) { 9 if(lo > hi) return null; 10 int mid = lo + (hi - lo) / 2; 11 TreeNode root = new TreeNode(nums[mid]); 12 root.left = helper(nums,lo,mid-1); 13 root.right = helper(nums,mid+1,hi); 14 return root; 15 } 16 }
1099 Build A Binary Search Tree
1099 Build A Binary Search Tree (30)（30 分）
代码：
#include <cstdio> #include <queue> #include <algorithm> using namespace std; const int N=105; struct Node{ int val; int left,right; }Tree[N]; int data[N]; int n; void inorderTraversal(int root) { static int idx=0; if(root!=-1){ inorderTraversal(Tree[root].left); Tree[root].val=data[idx++]; inorderTraversal(Tree[root].right); } } void layerOrderTraversal(int root) { int idx=0; queue<int> q; q.push(root); while(!q.empty()){ int top=q.front(); q.pop(); printf("%d",Tree[top].val); idx++; if(idx<n) printf(" "); if(Tree[top].left!=-1) q.push(Tree[top].left); if(Tree[top].right!=-1) q.push(Tree[top].right); } } int main() { scanf("%d",&n); int u,v; for(int i=0;i<n;i++){ scanf("%d%d",&u,&v); Tree[i].left=u; Tree[i].right=v; } for(int i=0;i<n;i++) scanf("%d",&data[i]); sort(data,data+n); inorderTraversal(0);//中序遍历，填入数据 layerOrderTraversal(0); return 0; }
1099 Build A Binary Search Tree (30)
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
The left subtree of a node contains only nodes with keys less than the node‘s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node‘s key.
Both the left and right subtrees must also be binary search trees.
Given the structure of a binary tree and a sequence of distinct integer keys,there is only one way to fill these keys into the tree so that the resulting tree satisfies the deFinition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by figure 1 and 2.
Input Specification:
Each input file contains one test case. For each case,the first line gives a positive integer N (<=100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format "left_index right_index",provided that the nodes are numbered from 0 to N-1,and 0 is always the root. If one child is missing,then -1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.
Output Specification:
For each test case,print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space,with no extra space at the end of the line.
Sample Input:
9 1 6 2 3 -1 -1 -1 4 5 -1 -1 -1 7 -1 -1 8 -1 -1 73 45 11 58 82 25 67 38 42
Sample Output:
58 25 82 11 38 67 45 73 42
#include<cstdio> #include<queue> #include<algorithm> using namespace std; const int maxn = 110; struct Node{ int data; int lchild,rchild; }node[maxn]; int n,in[maxn],num = 0; void inorder(int root){ if(root == -1) return; inorder(node[root].lchild); node[root].data = in[num++]; inorder(node[root].rchild); } void BFS(int root){ queue<int> Q; Q.push(root); int num = 0; while(!Q.empty()){ int Now = Q.front(); Q.pop(); printf("%d",node[Now].data); num++; if(num < n) printf(" "); if(node[Now].lchild != -1) Q.push(node[Now].lchild); if(node[Now].rchild != -1) Q.push(node[Now].rchild); } } int main(){ int lchild,rchild; scanf("%d",&n); for(int i = 0; i < n; i++){ scanf("%d%d",&lchild,&rchild); node[i].lchild = lchild; node[i].rchild = rchild; } for(int i = 0; i < n; i++){ scanf("%d",&in[i]); } sort(in,in+n); inorder(0); BFS(0); return 0; }
1099 Build A Binary Search Tree （30 分）
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
- The left subtree of a node contains only nodes with keys less than the node‘s key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node‘s key.
- Both the left and right subtrees must also be binary search trees.
Given the structure of a binary tree and a sequence of distinct integer keys,there is only one way to fill these keys into the tree so that the resulting tree satisfies the deFinition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by figure 1 and 2.
Input Specification:
Each input file contains one test case. For each case,the first line gives a positive integer N (≤100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format left_index right_index,provided that the nodes are numbered from 0 to N?1,and 0 is always the root. If one child is missing,then ?1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.
Output Specification:
For each test case,print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space,with no extra space at the end of the line.
Sample Input:
9 1 6 2 3 -1 -1 -1 4 5 -1 -1 -1 7 -1 -1 8 -1 -1 73 45 11 58 82 25 67 38 42
Sample Output:
思路：
这个题目要求输出二叉搜索树的层序遍历。我的思路是先建树，然后层次遍历即可。怎么建立一颗二叉搜索树呢？根据二叉搜索树的中序
遍历结果是有序的，所以进行中序遍历建立二叉树。题目中的输入告诉了我们二叉树的形状（每个结点的左右子女索引值都告诉我们了），所以
只需要对最后的一个key值序列进行排序，然后中序遍历赋值即可。
58 25 82 11 38 67 45 73 42
#include<iostream> #include<vector> #include<algorithm> #include<queue> #include<string> #include<map> #include<set> using namespace std; int tree[101]; //对树进行深度遍历 struct Node { int data; int lchild; int rchild; }; int k=0; void inorder(Node node[],int key[],int i) { if(i!=-1) { inorder(node,key,node[i].lchild); node[i].data=key[k++]; inorder(node,node[i].rchild); } } vector<int> print; void level(Node node[]) { queue<int> q; q.push(0); while(!q.empty()) { int temp=q.front(); q.pop(); print.push_back(node[temp].data); if(node[temp].lchild!=-1) q.push(node[temp].lchild); if(node[temp].rchild!=-1) q.push(node[temp].rchild); } } int main() { int n; cin>>n; Node node[n]; for(int i=0;i<n;i++) { cin>>node[i].lchild>>node[i].rchild; } int key[n]; for(int i=0;i<n;i++) cin>>key[i]; sort(key,key+n); inorder(node,0); level(node); cout<<print[0]; for(int i=1;i<print.size();i++) cout<<" "<<print[i]; return 0; }
今天关于99. Recover Binary Search Tree的讲解已经结束，谢谢您的阅读，如果想了解更多关于108. Convert Sorted Array to Binary Search Tree、1099 Build A Binary Search Tree、1099 Build A Binary Search Tree (30)、1099 Build A Binary Search Tree （30 分）的相关知识，请在本站搜索。
本文标签：
