题目描述
给你二叉搜索树的根节点 root
,该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树 。
思路
和 98. 验证二叉搜索树一样,中序遍历正好可以按递增的顺序对比节点,这样只需要记录有问题的节点即可。
由于恰好只有两个值被交换了,那么一定有一个是比它前后的数大的,也有一个比它前后的数小的。
那么中序遍历一次,一定能找到比他前后数字都大的,但是可能有多个比它前后数字都小的,此时我们取最后一个。
最终代码:
搜索
给你二叉搜索树的根节点 root
,该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树 。
和 98. 验证二叉搜索树一样,中序遍历正好可以按递增的顺序对比节点,这样只需要记录有问题的节点即可。
由于恰好只有两个值被交换了,那么一定有一个是比它前后的数大的,也有一个比它前后的数小的。
那么中序遍历一次,一定能找到比他前后数字都大的,但是可能有多个比它前后数字都小的,此时我们取最后一个。
最终代码: