NC58 找到搜索二叉树中两个错误的节点
情景提要
牛客题解系列,按照题号顺序开始。
NC58 找到搜索二叉树中两个错误的节点
01
题目描述
一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请按升序输出这两个错误节点的值。(每个节点的值各不相同)
02
输入输出示例
输入:
{1,2,3}
输出:
[1,2]
03
题目分析
思路
对搜索二叉树进行中序遍历,会得到一个有序数组。
本题可以按照中序遍历顺序,遍历整个二叉树,找到大小错位的那个,即为结果。但有一个问题,调换位置的两个节点不一定相邻。如果只是遍历并不存储,就只能找到第一个。或者需要再右中左遍历找到第二个。
本题使用一个数组存储遍历结果,接着从左向右遍历,找第一个错位的数,再从右向左遍历,找第二个错位的数。错位数字在数组中的index大小是可以通过实际的模拟来确定。
肯定是把前面一个小的数与后面一个大的数换位置了。
以{1,2,3}为例,中序遍历结果[2,1,3].
从左向右遍历找大的数。2>1 被换的大的数是2.
从右向左遍历找小的数。1<2 被换的小的数是1.
也可以模拟一个所换数字不相邻的情况,就更明显了。
由于遍历过程中,可能首尾元素遍历不到,因此可以将首尾元素作为返回结果的初始化。
而实际情况下,如果结果存在,那么被换的小的元素一定不会在首,被换的大的元素一定不会在尾。即可以不用初始化,在遍历的过程中一定会找到被换的元素。
03
代码实现
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return int整型vector
*/
//二叉搜索数的中序遍历应该是一个有序数组
vector<int> findError(TreeNode* root) {
// write code here
stack<TreeNode*> st;
TreeNode* node = root;
if(root) st.push(root);
vector<int> res;
while(!st.empty()){
node = st.top();
st.pop();
if(node){
if(node->right) st.push(node->right);
st.push(node);
st.push(nullptr);
if(node->left) st.push(node->left);
}else{
node = st.top();
st.pop();
res.push_back(node->val);
}
}
vector<int> ret(2,0);
ret[0] = res[0];
ret[1] = res[res.size()-1];
for(int i=1;i<res.size();++i){
if(res[i]<res[i-1]) {
ret[1] = res[i-1];
break;
}
}
for(int i=res.size()-1;i>=1;--i){
if(res[i]<res[i-1]) {
ret[0] = res[i];
break;
}
}
return ret;
}
};
04
总结
要考虑到被换的节点不一定相邻,因此需要遍历两次。
欢迎评论区留言哦