阿Q的博客

[897] Increasing Order Search Tree

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

algorithms
Easy (58.75%)
Source Code: 897.increasing-order-search-tree.py
Total Accepted: 26.3K
Total Submissions: 41.3K
Testcase Example: '[5,3,6,2,4,null,8,1,null,null,null,7,9]'

Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

Example 1: Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

   5
  / \
3    6

/ \
2 4 8 / / \ 1 7 9

Output: [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

Note:

The number of nodes in the given tree will be between 1 and 100.
Each node will have a unique integer value from 0 to 1000.

python

# 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 increasingBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root: return None

        result = []

        def inorder(root):
            if not root: return
            if root.left:
                inorder(root.left)
            result.append(root.val)
            if root.right:
                inorder(root.right)

        inorder(root)

        if not result: return None

        head = TreeNode(result[0])
        p = head
        tail = None

        for item in result[1:]:
            tail = TreeNode(item)
            p.right = tail
            p = tail

        if tail:
            tail.right = None

        return head