Description: You are given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Follow up: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
Link: 99. Recover Binary Search Tree
Examples:
Example 1:
Input: root = [1,3,null,null,2] Output: [3,1,null,null,2] Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid. Example 2:
Input: root = [3,1,4,null,null,2] Output: [2,1,4,null,null,3] Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
思路: 想到二叉搜索树的顺序排列，就想到前几天做的中序遍历是升序排列，所以用中序遍历，如果不是升序的，那位置肯定不对。但是我只能想到遍历出来是list,然后在list中是可以找到两个顺序错了的元素，可怎么和二叉树的节点对应回去呢？不会，不会，看题解吧。豁然开朗。
因为对树的认识理解太浅，想到遍历就只想着要输出节点的值，放在熟悉的list里看，但是遍历只是手段，遍历里要做什么取决于目的。这个题目的目的就是在遍历中找到两个位置错了的节点，那么在中序遍历中什么条件来判断位置错了？就是前一个节点的值大于当前节点值，所以我们记录前一个节点pre，第一个错的节点first, 和第二个错的节点second。
举个例子，[1,4,3,2,5],遍历到3，返现pre=4 > 3, 所以first = pre, 遍历到2，发现pre = 3 > 2， 所以second = current node 2，值得注意的是，第一个节点赋值pre,第二个是当前节点，而不是pre.
所以整个过程还是递归的中序遍历，但在遍历的内部对当前节点要完成的任务是，判断当前节点或前一个节点是否位置不对，而不是输出val, 遍历结束得到位置不对的节点后，将其val值互换即可。
class Solution(object): def recoverTree(self, root): """ :type root: TreeNode :rtype: None Do not return anything, modify root in-place instead. """ self.pre, self.first, self.second = None, None, None self.Inorder(root) self.first.val, self.second.val = self.second.val, self.first.val def Inorder(self, root): if not root: return self.Inorder(root.left) if self.pre and self.pre.val > root.val: if not self.first: self.first = self.pre self.second = root self.pre = root self.Inorder(root.right)
日期: 2021-03-16 从别人那里学到不会的东西，有了新的感悟，真开心！希望我不要逃避，好好努力