A.每日一题——1382. 将二叉搜索树变平衡

题目链接：1382. 将二叉搜索树变平衡（中等）

算法原理：

解法：递归

2ms击败100.00%

时间复杂度O(N)

①题目明确是二叉搜索树，则节点值天然满足：左子树<根<右子树，因此通过一次A.每日一题——94. 二叉树的中序遍历，直接把节点都扔进数组里，就是天然升序的

②再通过A.每日一题——108. 将有序数组转换为二叉搜索树转化成平衡树即可

Java代码：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode balanceBST(TreeNode root) { List<Integer> nums=inorder(root); return sorttoBST(nums); } //中序遍历 private List<Integer> inorder(TreeNode root){ List<Integer> ret=new ArrayList<>(); dfs(ret,root); return ret; } private void dfs(List<Integer> ret,TreeNode node){ if(node==null) return ; dfs(ret,node.left); ret.add(node.val); dfs(ret,node.right); } //将有序数组转换成二叉搜索树 private TreeNode sorttoBST(List<Integer> nums){ return build(nums,0,nums.size()); } private TreeNode build(List<Integer> nums,int left,int right){ if(left==right) return null; int mid=left+(right-left)/2; return new TreeNode(nums.get(mid),build(nums,left,mid),build(nums,mid+1,right)); } }