LeetCode日本語修行12日目- [897-二分木通りがけ順をします]


Increasing Order Search Tree

参考:https://leetcode.com/problems/increasing-order-search-tree/

問題の内容:

二分木Root、Rootの一番左のノードが木の根になり、すべてのノードの左の子はNULLで、右の子を1つだけ持つように、木を順に並べ替える。

例:

例1:
Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

      5
   3     6
 2   4     8
1        7   9

以下に変換:

 1
  2
   3
    4
     5
      6
       7
        8
         9

例2:
Input: root = [5,1,7]
Output: [1,null,5,null,7]
左の子はNULLで,nullで表示します

ヒント:

The number of nodes in the given tree will be in the range [1, 100].
0 <= Node.val <= 1000


他のやり方もありますが、イテレーションを使います。。。


/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {

    fun increasingBST(root: TreeNode?): TreeNode? {
         return inorder(root,null)
    }

    fun inorder(root: TreeNode?,pre: TreeNode?): TreeNode? {
        if(root == null){
            return pre
        }

        var currentValue =  inorder(root?.left,root)
        root?.left = null
        root?.right = inorder(root?.right,pre)
        return currentValue
    }
}