Python C++ InOrder與Greedy解Leetcode 1382 Balance a Binary Search Tree

Python C++ InOrder與Greedy解Leetcode 1382  Balance a Binary Search Tree

使用中序/逆中序走訪建立按升序/降序排序的 int 陣列。

貪婪演算法（分而治之）建構平衡的 BST。

Python code請進

-----

Use inorder/reverse-inorder transverals to create a sorted int array in increasing/decreasing order.

Greedy method (divide & conquer) builds a balanced BST.

[codes on Leetcode]https://leetcode.com/problems/balance-a-binary-search-tree/solutions/5369849/inorder-greedy-balanced-bst-45ms-beats-100/

[Tree & Graph Playlist]https://www.youtube.com/watch?v=9Lx7yr-tmfI&list=PLYRlUBnWnd5Kt0-3un43cwY6yT_il8NWe

[Leetcode程式 playlist]https://www.youtube.com/watch?v=527BNZYm6aE&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk&index=3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        arr=[]
        def inorder(root):
            if root==None: return
            inorder(root.left)
            arr.append(root.val)
            inorder(root.right)
        def BST(l, r):
            if l>r: return None
            m=(l+r)//2
            left=BST(l, m-1)
            right=BST(m+1, r)
            return TreeNode(arr[m], left, right)
        
        inorder(root)
        return BST(0, len(arr)-1)