X

LEETCODE 1382. Balance a Binary Search Tree

题目大意:

将二叉搜索树变平衡

给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。

如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 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] 也是一个可行的构造方案。

提示:

  • 树节点的数目在 110^4 之间。
  • 树节点的值互不相同,且在 110^5 之间。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1382

解题思路分析:

这道题难度不大,我们需要两个步骤,第一,先将原始的二叉搜索树还原成数组,该数组是升序排序的。然后我们再使用二分法重组二叉树即可。

解题时,将二叉查找树变成排序数组的方式是使用中序遍历(递归左子节点,打印当前节点节点,递归右子节点顺序)。还原二叉查找树时,我们同样需要使用到递归,递归方法中首先取出数组中间值为二叉树根节点,然后以当前下标将数组一分为二,左半边递归到子问题,它的返回值为当前节点的左子节点,右半部分同样递归到子问题,它的返回值为当前节点的右子节点。

实现代码:

// 存储二叉树所有节点
List<Integer> list=new ArrayList<>();
public TreeNode balanceBST(TreeNode root) {
    // 中序遍历二叉树,取得树中所有节点
    inOrder(root);
    // 使用二分递归,新建二叉搜索树
    return help(0,list.size()-1);
}
void inOrder(TreeNode root){
    if(root.left!=null) inOrder(root.left);
    list.add(root.val);
    if(root.right!=null) inOrder(root.right);
}
// l:二分范围左边界
// r:二分范围右边界
TreeNode help(int l, int r){
    // 区间范围不合理,返回空
    if(l>r) return null;
    // 取得中间点
    int mid=(l+r)/2;
    // 中间点为当前节点
    TreeNode node = new TreeNode(list.get(mid));
    // 利用当前节点,将区间分为左右两部分
    // 将左半部分递归至子问题,其返回值为当前节点左子节点
    node.left=help(l,mid-1);
    // 将右半部分递归至子问题,其返回值为当前节点右子节点
    node.right=help(mid+1,r);
    // 返回当前节点
    return node;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 99.76% of Java online submissions for Balance a Binary Search Tree.

Memory Usage: 43.5 MB, less than 100.00% of Java online submissions for Balance a Binary Search Tree.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1382-balance-a-binary-search-tree/
Categories: leetcode
kwantong: