题解 | #找到搜索二叉树中两个错误的节点#
找到搜索二叉树中两个错误的节点
https://www.nowcoder.com/practice/4582efa5ffe949cc80c136eeb78795d6
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ #include <climits> class Solution { public: /** * * @param root TreeNode类 the root * @return int整型vector */ TreeNode* t1 = nullptr; //记录第一个错误点 TreeNode* t2 = nullptr; //记录第二个错误点 TreeNode* temp = nullptr; //记录中序遍历中,当前结点的上一个结点 int max = INT_MIN; bool flag = false; //用于区别第一次找到错误点和第二次找到错误点 void findT(TreeNode* root){ if(root->left != nullptr){ findT(root->left); } if(max > root->val && flag == false){ //如果第一次找到错误点,则先假设交换的两个点是相邻点 t1 = temp; t2 = root; flag = true; }else if(max > root->val){ //如果不是交换的两个点不是相邻点则会进入该条件 t2 = root; } temp = root; //在进入下一轮递归前,将当前结点记录下来 max = root->val; if(root->right != nullptr){ findT(root->right); } } vector<int> findError(TreeNode* root) { // write code here vector<int> answer; findT(root); answer.push_back(t2->val); answer.push_back(t1->val); return answer; } };
看c++的题解中好像空间复杂度都是O(n),小伙子就献丑一下(●'◡'●)
空间复杂度为O(n)的题解中的思路都是,用中序遍历和vector来将搜索二叉树记录下来,
然后找到一个错误点(相邻结点交换) 如:(1,2,3,5,4,6,7)
或者两个错误点(非相邻结点交换)。 如:(1,2,6,4,5,3,7)
如果是一个错误点(4),则将错误处(4)和错误处的前一个结点(5)作为答案返回
如果是两个错误结点(4,3),则将第一个错误结点的前一个结点(6)和第二个错误结点(3)作为答案返回
空间复杂度为O(1)的思路是,用一个结点指针temp记录中序遍历中当前结点的上一个结点
当第一次遇到错误结点时,将错误结点和错误结点的前一个结点记录下来
如果接下来的遍历不在碰到错误结点时,则直接返回前面记录下来的两个结点
如果接下来再次碰到错误结点,则将当前错误结点和第一次碰到的错误结点的前一个结点作为答案