https://leetcode.com/problems/balance-a-binary-search-tree
給定一二元搜尋樹 請回傳有相同節點值的平衡二元搜尋樹
如果有多個 請回傳任一個即可
假如左右子樹深度相差不超過1 此即為平衡二元搜尋樹
Example 1:
Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also
correct.
Example 2:
Input: root = [2,1,3]
Output: [2,1,3]
思路:
先用dfs遍歷整棵樹 記錄所有節點的值
之後再重新建一顆符合要求的平衡二元搜尋樹
Python Code:
# 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:
def dfs(node):
if not node:
return []
else:
return dfs(node.left) + [node.val] + dfs(node.right)
values = dfs(root)
def build_balanced_bst(vals):
if not vals:
return None
mid = len(vals) // 2
node = TreeNode(vals[mid])
node.left = build_balanced_bst(vals[:mid])
node.right = build_balanced_bst(vals[mid+1:])
return node
return build_balanced_bst(values)