【LeetCode】99. Recover Binary Search Tree 解题报告(Python)

【LeetCode】99. Recover Binary Search Tree 解题报告(Python)

标签(空格分隔): LeetCode


题目地址:https://leetcode.com/problems/recover-binary-search-tree/description/

题目描述:

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

题目大意

删除二叉树中指定一节点,并调整二叉树,使得结果的二叉树仍然满足BST的条件。

解题方法

同学们,看到BST就想什么?对,中序遍历是有序的。

那么,如果其中两个被交换了,那么中序遍历的结果一定也就不对了。比如:

[1, 2, 3, 4, 5, 6]  ==>  [1, 5, 3, 4, 2, 6]

那么,可以看出5这个数字比后面的3大,说明他被打乱了;另外2这个数字,比前面的数字4小,所以他也被打乱了。

所以,可以通过先进行中序遍历得到所有的,然后再查找哪些乱了,再复原,时间复杂度O(n)。

但是,中序遍历的操作不需要完全完成。在中序遍历的过程中,用一个指针保存上个节点,那么当前节点值应该小于前一个节点的值。否则就存在乱序。

第一个乱序的数字是pre,第二个乱序的数字是root,所以用两个指针分别保存。

代码:

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution(object):
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void 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)

日期

2018 年 3 月 23 日 ———— 科目一考了100分哈哈哈哈~嗝~

上一篇:【leetcode】Recover Binary Search Tree


下一篇:ClickOnce添加自定义prerequisite