各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 86 天。今天力扣上的每日一题是「897. 递增顺序搜索树」。

解题思路

题意：把一棵「二叉搜索树」按照中序遍历构成一棵每个节点都只有右孩子的树。与不久前的每日一题「783. 二叉搜索树节点最小距离」是极其相似的题目。

遇到二叉搜索树，立刻想到这句话：「二叉搜索树（BST）的中序遍历是有序的」。这是解决所有二叉搜索树问题的关键。

本题已经告诉我们使用中序遍历，其实对于二叉搜索树而言，只要让我们得到有序的遍历结果，那么一定要想到中序遍历。

分享二叉树遍历的经验：先序、中序、后序遍历方式的区别在于把「执行操作」放在两个递归函数的位置。伪代码在下面。

  1. 先序遍历：
    1. def dfs(root):
    2.  if not root:
    3.      return
    4.  执行操作
    5.  dfs(root.left)
    6.  dfs(root.right)

  2. 中序遍历：

    1. def dfs(root):
    2.  if not root:
    3.      return
    4.  dfs(root.left)
    5.  执行操作
    6.  dfs(root.right)

  3. 后序遍历：

    1. def dfs(root):
    2.  if not root:
    3.      return
    4.  dfs(root.left)
    5.  dfs(root.right)
    6.  执行操作

本题是使用了中序遍历，所以把「执行操作」这一步改成自己想要的代码。用本题作为示例。

于是有了下面两种写法。

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

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

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

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

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution(object):
  9.     def increasingBST(self, root):
  10.         self.res = []
  11.         self.inOrder(root)
  12.         if not self.res:
  13.             return 
  14.         dummy = TreeNode(-1)
  15.         cur = dummy
  16.         for node in self.res:
  17.             node.left = node.right = None
  18.             cur.right = node
  19.             cur = cur.right
  20.         return dummy.right
  22.     def inOrder(self, root):
  23.         if not root:
  24.             return
  25.         self.inOrder(root.left)
  26.         self.res.append(root)
  27.         self.inOrder(root.right)
  • 时间复杂度：$O(N)$，因为每个节点只访问了一次；
  • 空间复杂度：$O(N)$，因为需要数组保存二叉树的每个节点值。

方法二：只保存上个节点

在方法一中，我们保存了整个中序遍历数组，比较浪费空间。

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

所以，我们只需要一个变量 prev 保存在中序遍历时，上一次被访问的节点。那么我们每次遍历的时候，都要把 prev.right 设置为当前遍历的节点 root，把当前节点 root.left 设置为 null。这样的话，就保证了在中序遍历的过程中的访问顺序，形成了一个新的只有右孩子的树。

同样地，我们设置一个 dummy 节点当做新的树的根节点，并把它作为默认的 prev 节点。

代码如下：

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution(object):
  9.     def increasingBST(self, root):
  10.         dummy = TreeNode(-1)
  11.         self.prev = dummy
  12.         self.inOrder(root)
  13.         return dummy.right
  15.     def inOrder(self, root):
  16.         if not root:
  17.             return None
  18.         self.inOrder(root.left)
  19.         root.left = None
  20.         self.prev.right = root
  21.         self.prev = root
  22.         self.inOrder(root.right)
  • 时间复杂度：$O(N)$，因为每个节点只访问了一次；
  • 空间复杂度：$O(N)$，因为递归用了系统栈。

    刷题心得

在最近几个月的刷每日一题的过程中，已经发现有多次题目都是高度类似的。掌握一道题，掌握一种方法，然后反复练习，下次再遇到类似的题目，应该就会做了。

参考资料：
897. Increasing Order Search Tree

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！