vlambda博客
学习文章列表

NC58 找到搜索二叉树中两个错误的节点

情景提要

    牛客题解系列,按照题号顺序开始。







NC58 找到搜索二叉树中两个错误的节点








01




题目描述

     一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请按升序输出这两个错误节点的值。(每个节点的值各不相同)


02




输入输出示例

输入:

    {1,2,3}

输出: 

    [1,2]


03




题目分析


思路


    对搜索二叉树进行中序遍历,会得到一个有序数组。

    本题可以按照中序遍历顺序,遍历整个二叉树,找到大小错位的那个,即为结果。但有一个问题,调换位置的两个节点不一定相邻。如果只是遍历并不存储,就只能找到第一个。或者需要再右中左遍历找到第二个。

   本题使用一个数组存储遍历结果,接着从左向右遍历,找第一个错位的数,再从右向左遍历,找第二个错位的数。错位数字在数组中的index大小是可以通过实际的模拟来确定。

NC58 找到搜索二叉树中两个错误的节点














     肯定是把前面一个小的数与后面一个大的数换位置了。

     以{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




NC58 找到搜索二叉树中两个错误的节点

     要考虑到被换的节点不一定相邻,因此需要遍历两次。

NC58 找到搜索二叉树中两个错误的节点


NC58 找到搜索二叉树中两个错误的节点

NC58 找到搜索二叉树中两个错误的节点




欢迎评论区留言哦