本文共 1022 字，大约阅读时间需要 3 分钟。

题目：给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

解题思路一、对其中序遍历存储其所有结点的值，对其中的值进行遍历，存储器异常值，对树进行遍历，找到异常值，并进行替换。

public void recoverTree(TreeNode root) {
   		List
   
     nums = new ArrayList<>();		inorder(root,nums);		// 获取不正确的两个位置		int[] swapped = findTwoSwapped(nums);		recover(root,2,swapped[0],swapped[1]);    }		// 中序遍历获取结果	public void inorder(TreeNode root,List
    
      nums) {
   		if(root==null) {
   			return;		}		inorder(root.left,nums);		nums.add(root.val);		inorder(root.right,nums);	}		// 获得中序遍历不确定的两个位置	public int[] findTwoSwapped(List
     
       nums) {
   		int n = nums.size();		int x = -1,y=-1;;		for(int i=0;i
     
    
   

题解二、中序遍历的隐式遍历过程中寻找其异常值。

// 二叉搜索树的隐式恢复	public void recoverTree_2(TreeNode root) {
   		Stack
   
     stack = new Stack<>();		TreeNode x = null, y = null, pred= null;		while(!stack.isEmpty()||root!=null) {
   			while(root!=null) {
   				stack.push(root);				root = root.left;			}			root = stack.pop();			if(pred!=null&&root.val
   

转载地址：https://codingchaozhang.blog.csdn.net/article/details/109499745 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！