本文主要是介绍2种解法 - 将二叉搜索树变平衡，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 题目
- 调试工具
- 解法一（二分法构建平衡树）
- 解法二（中序遍历解析树结构）
- 解法三（二叉树旋转）
题目
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
如果有多种构造方法，请你返回任意一种。
示例：
输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
调试工具
为了方便代码调试，写了2个调试工具，分别为：
- 将输入的数组转为树结构（用于直接使用数组作为输入）
- 将一个树结构转换为字符串（用于打印查看树结构）
//调用方式
//TreeNode tree = null;
//GenerateTreeByOrder(new int?[]{1,null,15,14,17,7,null,null,null,2,12,null,3,9,null,null,null,null,11},out tree);
static void GenerateTreeByOrder(int?[] arr, out TreeNode tree)
{//基于顺序访问，使用数组创建二叉树int count = arr.Length;Queue<TreeNode> queue = new Queue<TreeNode>();tree = new TreeNode(arr[0].Value);queue.Enqueue(tree);int idx = 1; while(queue.Count > 0 && idx < count){TreeNode tmpTree = queue.Dequeue();if(!(arr[idx] is null)){//第一个是左子树tmpTree.left = new TreeNode(arr[idx].Value);queue.Enqueue(tmpTree.left);}if(!(arr[idx + 1] is null)){//第二个是右子树tmpTree.right = new TreeNode(arr[idx + 1]这篇关于2种解法 - 将二叉搜索树变平衡的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
