题解 | #找到搜索二叉树中两个错误的节点#
找到搜索二叉树中两个错误的节点
http://www.nowcoder.com/practice/4582efa5ffe949cc80c136eeb78795d6
算法思想一：中序遍历+数组
解题思路：
先求出中序遍历，然后根据中序遍历的结果求出异常值
1. 先用中序遍历遍历树，得到一个部分排序数组，该数组中有两个数交换了位置，现在的问题变成了从一个部分有序的数组中找出交换了位置的那两个数
2. 因为此时的情况必定是一个小的数放到了后面，一个大的数放到了前面所以从左往右找那个大的数，并记录下索引，从右往左找小的那个数，并且索引值必大于前面记录下的索引
2. 因为此时的情况必定是一个小的数放到了后面，一个大的数放到了前面所以从左往右找那个大的数，并记录下索引，从右往左找小的那个数，并且索引值必大于前面记录下的索引
代码展示：
Python版本
class Solution: def findError(self , root ): # write code here if not root: return [] res = [] stack = [] while stack&nbs***bsp;root: while root: stack.append(root) root = root.left root = stack.pop() # 中序遍历结果 res.append(root.val) root = root.right ans = [] # 查找两个错误节点 for i in range(len(res)-2, -1, -1): if res[i] > res[i+1]: ans.append(res[i+1]) break for i in range(1, len(res)): if res[i] < res[i-1]: ans.append(res[i-1]) break return ans
复杂度分析
时间复杂度O(N)：N表示二叉树节点数量，递归遍历所有节点，遍历整个数组
空间复杂度O(N)：辅助空间数组
算法思想二：递归+判断
解题思路：
直接在递归的过程中求出异常值 因为二叉搜索树的中序遍历是正序数组，所以直接进行中序遍历，遍历的过程中直接找出异常值分析结果可得，必然是一个较大的异常值交换到了前面，较小的异常值数放到了后面， 所以遍历的过程中出现的第一个当前值小于前一个值的情况时，前一个值即为要找的较大的异常值，而出现的最后一个 当前值小于前一个值的情况时，当前值才是我们要找的较小的异常值，所以在遍历过程中需要覆盖前面所求的较小值。
代码展示：
JAVA版本
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类 the root
* @return int整型一维数组
*/
int[] result = new int[2];
int index = 1;
TreeNode preNode;
public int[] findError (TreeNode root) {
// write code here
if(root == null) {
return result;
}
// 递归左子树
findError(root.left);
if(preNode == null) {
preNode = root;
}
// 判断是否是出错的节点
if(index == 1 && root.val < preNode.val) {
result[index] = preNode.val;
index--;
}
if(index == 0 && root.val < preNode.val) {
result[index] = root.val;
}
preNode = root;
// 递归右子树
findError(root.right);
return result;
}
} C++版本
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return int整型vector
*/
vector<int> v;
vector<int> res;
int flag=0;
void zhongxu(TreeNode* root){
if(root==nullptr) return;
zhongxu(root->left);
if(flag==2) return;
if(!v.empty()&&root->val<v[v.size()-1]){
if(flag==0){
res.push_back(root->val);
res.push_back(v[v.size()-1]);
flag=1;
}else{
res[0]=root->val;
flag=2;
}
}
if(flag==2) return;
v.push_back(root->val);
zhongxu(root->right);
}
vector<int> findError(TreeNode* root) {
// write code here
zhongxu(root);
return res;
}
}; 复杂度分析
时间复杂度O(N)：N表示二叉树节点数量，递归遍历所有节点
空间复杂度O(1)：不需要额外空间
海康威视工作强度 84人发布