Leetcode 99. 恢复搜索二叉树
Time: 20190901题目描述二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下恢复这棵树。示例 1:输入: [1,3,null,null,2]1/3\2输出: [3,1,null,null,2]3/1\2示例 2:输入: [3,1,4,null,null,2]3/\14/2输出: [2,1,4,null,null,3]2/\14/3进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗来源力扣LeetCode链接https://leetcode-cn.com/problems/recover-binary-search-tree著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。思路搜索过程中重建。根据搜索二叉树的形状在DFS遍历过程中如果出现当前结点比左孩子小或者比右孩子大时就考虑交换。但是当前视角是局部的交换之后会对上面产生影响又需要重新再过滤。其实解决方法很简单用中序遍历的结果来判断即可。在中序遍历序列中第一个错误的结点是在当前值大于后面的值取当前结点。第二个错误的结点是在当前值大于后面的值取后面结点。用全局变量跟踪两个结点然后交换值即可。代码# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val x# self.left None# self.right NoneclassSolution:defrecoverTree(self,root:TreeNode)-None: Do not return anything, modify root in-place instead. self.firstNoneself.secondNoneself.preTreeNode(float(-inf))definorder(root):ifnotroot:returninorder(root.left)ifself.preandself.pre.valroot.val:ifnotself.first:self.firstself.pre self.secondroot self.preroot inorder(root.right)inorder(root)self.first.val,self.second.valself.second.val,self.first.valEND.
