897.递增顺序查找树

题目#897.递增顺序查找树

给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
示例：
输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9  

题目分析

本题主要考察二叉树的中序遍历，中序遍历就是将二叉树的根节点操作顺序放在在左右子节点中间，用代码展示如下：

private fun dfs(root: TreeNode?, temp: TreeNode) {
    ...
    dfs(root.left, temp)
    // 中序遍历代码，操作root 
    dfs(root.right, t.right!!)
    ...
}

类似的，前序遍历就是根节点操作放在左右子节点前

private fun dfs(root: TreeNode?, temp: TreeNode) {
    ...
    // 前序遍历代码，操作root 
    ...
    dfs(root.left, temp)
    dfs(root.right, t.right!!)
    ...
}

后序遍历就是根节点操作放在在左右子节点后

private fun dfs(root: TreeNode?, temp: TreeNode) {
    ...
    dfs(root.left, temp)
    dfs(root.right, t.right!!)
    // 后序遍历代码，操作root 
    ...
}

既然已经明白了中序遍历，我们就可以根据题意确定递归函数的入参了：

确定函数入参

• 当前遍历到的节点root: TreeNode?
  我们要遍历这个二叉树，当前节点必不可少，我们传入的是root,是一个可空类型，所以声明为可空
• 保存的节点temp: TreeNode
  根据题意，我们需要将节点的每个值保存在一个新的二叉树中，所以这个参数也必不可少

确定了入参，让我们来想想两个老问题：

• 递归结束条件
  • 当前节点为空时递归结束if (root == null) return
• 递归体
  • 遍历左子树dfs(root.left, temp)
  • 将当前节点放在当前已经遍历的节点的最右边
    遍历完左子树，最右边的节点并不能简单的用temp.right表示，因为左边的节点并不只有一个
    我们需要手动的将节点的指针移动到最右边。使用一个while循环即可实现。
  • 遍历右子树dfs(root.right, node)

代码

class Solution {
    fun increasingBST(root: TreeNode?): TreeNode? {
        val res = TreeNode(0)
        dfs(root, res)
        return res.right
    }

    private fun dfs(root: TreeNode?, temp: TreeNode) {
        if (root == null) return
        dfs(root.left, temp)
        var t = temp
        while (t.right != null) {
            t = t.right!!
        }
        t.right = TreeNode(root.`val`)
        dfs(root.right, t.right!!)
    }
}