上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* balanceBST(TreeNode* root) {
}
};
python3 解法, 执行用时: 328 ms, 内存消耗: 21.9 MB, 提交时间: 2022-11-19 20:22:13
# 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 inorder(self, node):
if not node: return []
return self.inorder(node.left) + [node.val] + self.inorder(node.right)
def balanceBST(self, root: TreeNode) -> TreeNode:
nums = self.inorder(root)
def dfs(start, end):
if start == end: return TreeNode(nums[start])
if start > end: return None
mid = (start + end) // 2
root = TreeNode(nums[mid])
root.left = dfs(start, mid - 1)
root.right = dfs(mid + 1, end)
return root
return dfs(0, len(nums) - 1)
python3 解法, 执行用时: 300 ms, 内存消耗: 21.8 MB, 提交时间: 2022-11-19 20:20:41
# 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:
res = []
# 有序树转成有序数组
def traversal(cur: TreeNode):
if not cur: return
traversal(cur.left)
res.append(cur.val)
traversal(cur.right)
# 有序数组转成平衡二叉树
def getTree(nums: List, left, right):
if left > right: return
mid = left + (right -left) // 2
root = TreeNode(nums[mid])
root.left = getTree(nums, left, mid - 1)
root.right = getTree(nums, mid + 1, right)
return root
traversal(root)
return getTree(res, 0, len(res) - 1)
python3 解法, 执行用时: 304 ms, 内存消耗: 21.7 MB, 提交时间: 2022-11-19 20:19:37
# 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 getInorder(o):
if o.left:
getInorder(o.left)
inorderSeq.append(o.val)
if o.right:
getInorder(o.right)
def build(l, r):
mid = (l + r) // 2
o = TreeNode(inorderSeq[mid])
if l <= mid - 1:
o.left = build(l, mid - 1)
if mid + 1 <= r:
o.right = build(mid + 1, r)
return o
inorderSeq = list()
getInorder(root)
return build(0, len(inorderSeq) - 1)
