leetcode 99 恢复二叉搜索树
z
 2019-07-03 09:22:01  

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入: [1,3,null,null,2]

	 1
  /
 3
  \
   2
   
输出: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

进阶:

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

  • O(n)的时间复杂度

    正确的中序遍历得到的数组应该是升序的，因此，中序遍历后，将得到的数组排序即是正确的数值分配，再将每一个位置的数值赋值到对应的node中去即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    # 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: None Do not return anything, modify root in-place instead.
            """
            def dfs(root, nodeList, valueList):
                if not root:
                    return 
                if root.left:
                    dfs(root.left, nodeList, valueList)
                nodeList.append(root)
                valueList.append(root.val)
                if root.right:
                    dfs(root.right, nodeList, valueList)
                
            nodeList = []
            valueList = []
            dfs(root, nodeList, valueList)
            valueList.sort()
            for i, n in enumerate(valueList):
                nodeList[i].val = n

  • O(1)时间复杂度

    O(n)的复杂度主要来自于存储中序遍历的结果以及对应的Node顺序，有没有什么方法能够不保存顺序，直接找出需要交换数值的两个节点。

    对给定的这棵树：

    1
    2
    3
    4
    5
     1
     /
    3
     \
      2

    中序遍历的结果是

    1
    3, 2, 1

    需要交换的两个节点first 和last分别是：
    first: 相邻两个数中第一次出现 prev > cur 时的 prev
    last：在first出现之后，又一次出现 prev > cur 中的 cur

    1