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)