99. Recover Binary Search Tree

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的两个错误的节点，然后交换数值。值得注意的是，错误的节点有两种情况，比如开始中序遍历为1,2,3,4,5 1、中序遍历相邻，比如1,3,2,4,5。此时中序遍历只会存在一次错误。 2、中序遍历不相邻，比如1,4,3,2,5.此时中序遍历会出现两次错误。 所以在实际处理时，在遇到第一次错误时，记录两个节点；如果之后还有错误，更新节点。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution TreeNode m1, m2; //错误的两个值 TreeNode pre; //前一个节点，用于和当前节点比较，找出错误节 //findMistake功能：中序遍历，找出两个错误节点 void findMistake(TreeNode root) { if(root != null){ findMistake(root.left); if(pre != null && pre.val > root.val){ if(m1 == null){ //第一次遇到错误，记录两个节点 m1 = pre; m2 = root; } else { //再次出现错误，更新错误节点 m2 = root; } } pre = root; findMistake(root.right); } } public void recoverTree(TreeNode root) { findMistake(root); if(m1 != null && m2 != null) { //交换两个错误节点 int tmp = m1.val; m1.val = m2.val; m2.val

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。