算法第十一天-递增顺序搜索树

递增顺序搜索树

题目要求

解题思路

1.二叉搜索树（BST）
2.任意两个不同节点
遇到二叉搜索树，立即想到这句话：[二叉搜索树（BST）的中序遍历是有序的]。这是解决所有二叉搜索树问题的关键。

要求BST的任意两个不同节点之间的最小差值，也就是相当于求BST中序遍历得到的有序序列中所有相邻节点之间的最小差值。

分享二叉树遍历的经验：先序、中序、后序遍历方式的区别在于把[执行操作]放在两个递归的位置。
伪代码如下：
1.先序遍历

def dfs(root):
    if not root:
        return
    执行操作
    dfs(root.left)
    dfs(root.right)

2.中序遍历

def dfs(root):
    if not root:
        return
    dfs(root.left)
    执行操作
    dfs(root.right)

3.后序遍历

def dfs(root):
    if not root:
        return
    dfs(root.left)
    dfs(root.right)
	执行操作

本题使用了中序遍历，所以把[执行操作]这一步改成自己想要的代码。

方法一：数组保存中序遍历结果

这个方法最直观，也不容易出错。

1. 先中序遍历，把结果放在数组中；
   2.然后修改数组中每个节点的左右指针：把节点的左指针设置为null，把节点的右指针设置为数组的下一个节点。

下面代码中，使用了dummy(哑节点)，它一般在链表题中出现。在链表题目中，我们为了防止链表的头节点发生变化之后，不好维护头节点，我们设置dummy从而保证头节点不变。这个题目中设置了dummy，从而保证了在新的树中，dummy，从而保证了在新的树中，dummy是根节点，最终返回的时候，要返回的是dummy.right.

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    ## 通过数组进行保存中序遍历结果
    ## 时间复杂度：O(N);空间复杂度：O(N)
    def increasingBST(self, root: TreeNode) -> TreeNode:
        self.res=[]
        self.inOrder(root)
        if not self.res :
            return 
        dummy = TreeNode(-1)
        cur = dummy
        for node in self.res:
            node.left = node.right = None
            cur.right=node
            cur = cur.right
        return dummy.right
    def inOrder(self,root):
        if not root:
            return
        self.inOrder(root.left)
        self.res.append(root)
        self.inOrder(root.right)

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(N)$

方法二：

在方法一中，我们保存了整个中序遍历数组，比较浪费空间。其实我们只需要知道，在中序遍历的时候的两个被依次访问的节点。注意，这里说的不是BST的相邻节点，因为在中序遍历时，在访问根节点前，上一个被访问的节点时其左子树的最右下角的节点。如下图所示，访问 节点4 之前，访问的是 节点3

所以我们只需要一个变量prev保存在中序遍历时，上一次被访问的节点。那么我们每次遍历的时候：

• 把当前节点root.left设置为null;
• 把prev.right设置为当前遍历的节点root；
• 把当前root设置为prev

这样子的话，就保证了在中序遍历的过程中的访问顺序，形成了一个新的只有右孩子的树。
上图中，在完成中序遍历之后，新的树的结构就是按照图中的红色箭头.
代码中同样的，我们设置一个dummy节点当作新的树的根节点，并把它作为默认的prev节点。

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        dummy=TreeNode(-1)
        self.prev = dummy
        self.inOrder(root)
        return dummy.right
    def inOrder(self,root):
        if not root:
            return None
        self.inOrder(root.left)
        root.left = None
        self.prev.right =root
        self.prev =root
        self.inOrder(root.right)

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(N)$