【算法题解】64. 将二叉搜索树变平衡

❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/balance-a-binary-search-tree/

❞

题目

给你一棵二叉搜索树，请你返回一棵平衡后的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。

如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是平衡的。

示例 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：

输入: root = [2,1,3] 
输出: [2,1,3]

提示：

树节点的数目在范围内。

题解

这是一道中等难度的题，但是如果没有看清条件，直接上来就通过二叉树旋转来构建二叉平衡树，就会变成一道困难题。

注意题目给出的是二叉搜索树，根据二叉搜索树的特性，其中序遍历是一个有序序列。

所以最简单的解法就是先求出二叉搜索树中序遍历序列，也就是一个有序序列，然后根据这个有序序列来构造二叉平衡树。

一、求中序序列

求中序遍历序列的方法见题解：【算法题解】41. 二叉树的中序遍历。

由于题目给出的原始树是二叉搜索树，所以中序遍历最终会是一个有序序列，如示例一的中序序列为：[1, 2, 3, 4]。

二、根据有序序列构造二叉平衡搜索树

我们将有序序列的开始和结束位置分别记为 start 和 end。

取序列的中间点 mid 构建根节点 root。剩余左右两边节点数要么相等，要么只相差 1 个，所以肯定是平衡的。

然后再用 mid 左边的子序列构造二叉平衡搜索树作为 root 的左子树。

同样的，使用 mid 右边的子序列构造一棵二叉平衡搜索树作为 root 的右子树。

构造左右子树都是本问题的子问题，使用递归的思路解题。

递归边界条件：当序列为空时，直接返回空即可。

求中间节点的时候，当总数是奇数的时候刚好可以取到中间点。当总数是偶数的时候（如总数是4），取中间位置前后的节点都可以（如示例一中的 2 或者 3），这里我们统一去前面的点，即 ;

代码实现

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 {
    private List<Integer> inorderList = new ArrayList<>();
    public TreeNode balanceBST(TreeNode root) {
        inorder(root);
        return buidBalanceBST(0, inorderList.size() - 1);
    }

    private void inorder(TreeNode node){
        if(node == null){
            return;
        }
        inorder(node.left);
        inorderList.add(node.val);
        inorder(node.right);
    }

    private TreeNode buidBalanceBST(int start, int end){
        if(start > end){
            return null;
        }

        int mid = (start + end) >> 1;
        TreeNode node = new TreeNode(inorderList.get(mid));
        node.left = buidBalanceBST(start, mid - 1);
        node.right = buidBalanceBST(mid + 1, end);

        return node;
    }

 
}

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func balanceBST(root *TreeNode) *TreeNode {

    inorderList := []int{}

    var inorder func(node *TreeNode)

    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        inorderList = append(inorderList, node.Val)
        inorder(node.Right)
    }


    inorder(root)

    var buildBalanceBST func(start int, end int) *TreeNode 
    buildBalanceBST = func(start int, end int) *TreeNode {
        if start > end {
            return nil
        }

        mid := (start + end) / 2
        node := &TreeNode{inorderList[mid], nil, nil}
        node.Left = buildBalanceBST(start, mid - 1)
        node.Right = buildBalanceBST(mid + 1, end)

        return node
    }

    return buildBalanceBST(0, len(inorderList) - 1)
}