二叉搜尋樹(BST):它或者是一棵空樹,或者是具有下列性質的二叉樹: 若它的左子樹不空,則左子樹上所有結點的值均小于它的根結點的值; 若它的右子樹不空,則右子樹上所有結點的值均大于它的根結點的值; 它的左、右子樹也分别為二叉搜尋樹。
形如 4
/ \
2 6
/ \ / \
1 3 5 7
特點是其中序周遊是遞增的
利用遞歸思想中序周遊到第一個子節點:
public class Solution {
TreeNode pre=new TreeNode(Integer.MIN_VALUE);
TreeNode first=null;
TreeNode second=null;
public void recoverTree(TreeNode root) {
if(root==null)
return;
inorder(root);
int temp=first.val;
first.val=second.val;
second.val=temp;
}
public void inorder(TreeNode root){
if(root!=null){
inorder(root.left);
if(first==null&&pre.val>root.val){
first=pre;
}
if(first!=null&&pre.val>root.val){
second=root;
}
pre=root;
inorder(root.right);
}
}
}