Leetcode 108バランス二叉探索ツリー

2429 ワード

これから仕事を探して生きていくために、最近Leetcodeを磨き始めました..惨めで、まだTMDはPythonを使って、ブラシの問題はC++が使いやすいと感じます.以前はコンテストをやっていたのでしょうが、さすがに科班出身ではなく、データ構造の基礎が薄いです.正直、今日初めてバランス二叉探索樹の概念を聞きました(コンテストは二叉樹の問題が少ないのであまり見たことがありません..).
Leetcodeリンク:https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/description/
二叉探索木とは、以下の3つの条件がある.
1、左のノードが空でない場合、値はルートノードの値より小さい
2、右側のノードが空でない場合、ルートノードの値より大きい
3、左右のサブツリーも二叉検索ツリー
一方、バランスツリーは、ツリーに基づいて2つの条件を追加します.
1、左サブツリーと右サブツリーの深さの差が1以下
2、左右のサブツリーはバランス二叉木である
タイトルには順序付けされたリストがあります.バランス二叉検索ツリーを作成しましょう.リストを返すので、遍歴しなければなりません.並べ替えられたリストがあり、バランスツリーを構築するのは簡単で、考え方は簡単です.値をルートノードにし、残りの左のリストを左のサブツリーとして、右のリストは右サブツリー(検索ツリーの条件1,2をちょうど満たしている)として、再帰的にバランス二叉検索ツリー(二叉木問題再帰無敵と感じた..)を生成することができる.私はキューを使って、ノードを1つ読んで、それをキューから出して、その左右のノードを検索待ちキューに押し込む(必ずしも最良ではなく、でたらめな感じがlow).
前のコード:
#encoding=utf-8
import numpy as np

# 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 createTree(self, nums):
        if nums == []:
            return None
        n = len(nums)
        root = TreeNode(nums[n / 2])
        root.left = self.createTree(nums[0 : n/2])
        # print root.left.val
        root.right = self.createTree(nums[n/2+1 : n])
        # print root.left.val
        return root

    def searchTree(self, root):
        if root == None:
            return []
        Queue = [root]
        ans = [root.val]
        top = 0
        i = 0
        while i <= top:
            if Queue[i] == None:
                i += 1
                continue
            Queue.append(Queue[i].left)
            Queue.append(Queue[i].right)
            if Queue[i].left == None:
                ans.append(None)
            else:
                ans.append(Queue[i].left.val)
            if Queue[i].right == None:
                ans.append(None)
            else:
                ans.append(Queue[i].right.val)
            i += 1
            top += 2
        n = len(ans)
        while ans[n-1] == None:
            n -= 1
        return ans[0:n]

    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        root = self.createTree(nums)
        return self.searchTree(root)


# s = Solution()
# print s.sortedArrayToBST([-10,-3,0,5,9])