66 lines
2.7 KiB
JavaScript
66 lines
2.7 KiB
JavaScript
/**
|
||
* Definition for a binary tree node.
|
||
* function TreeNode(val, left, right) {
|
||
* this.val = (val === undefined ? 0 : val);
|
||
* this.left = (left === undefined ? null : left);
|
||
* this.right = (right === undefined ? null : right);
|
||
* }
|
||
*/
|
||
|
||
/**
|
||
* @param {TreeNode} root
|
||
* @return {TreeNode}
|
||
*/
|
||
const balanceBST = function (root) {
|
||
|
||
};
|
||
|
||
/*
|
||
现在不来考虑二叉搜索树变平衡，考虑一下给你一个有序的数组你如何将他变平衡，我的猜想是这样的，直接寻找找到数组序列的中间位置mid =Math.floor(left + right)
|
||
将mid作为这个根节点，将mid左侧的元素(不是小于等于)全部用来构建左子树，将mid右侧的元素全部用来构建右子树，之后在子树上重复这个过程，最后构建出来的树，
|
||
就是一棵平衡二叉搜索树，原因很简单，log2(k),和log2(k+1)的差不会超过1，一个区间被分割无外乎两种情况，左边和右边的数量相等，或者左边和右边的数量相差
|
||
1，这是满足平衡二叉树定义的，所以这种构建的贪心策略是合理的。
|
||
记住：一个有序的序列只要取中间值作为根节点，左右侧序列作为左右子树，之后递归处理左右子树，最终就能构建一颗平衡二叉搜索树，而二叉搜索树的中序遍历恰好
|
||
是有序序列，所以只需要将二叉搜索树遍历，之后拿到遍历的结果重新按照上面的方法构建一颗平衡二叉搜索(BST)树就行
|
||
*/
|
||
function TreeNode(val, left, right) {
|
||
this.val = (val === undefined ? 0 : val);
|
||
this.left = (left === undefined ? null : left);
|
||
this.right = (right === undefined ? null : right);
|
||
}
|
||
|
||
function f1(root) {
|
||
// 1.遍历二叉搜索树(BST)获取对应有序序列
|
||
const inorder = [];
|
||
const inorderTraversal = (root) => {
|
||
if (!root) return;
|
||
// 遍历左子树
|
||
inorderTraversal(root.left);
|
||
// 将中序遍历的值存入数组
|
||
inorder.push(root.val);
|
||
// 遍历右子树
|
||
inorderTraversal(root.right);
|
||
};
|
||
|
||
inorderTraversal(root); // 对原始树进行中序遍历
|
||
|
||
// 2.递归构建平衡二叉搜索树
|
||
const sortedArrayToBST = (left, right) => {
|
||
if (left > right) return null; // 当前区间不存在元素，无法构建子树
|
||
|
||
const mid = Math.floor((left + right) / 2);
|
||
// 为当前区间所有元素构建根节点
|
||
const curRoot = new TreeNode(inorder[mid]);
|
||
// 递归构建左子树
|
||
const leftNode = sortedArrayToBST(left, mid - 1);
|
||
// 递归构建右子树
|
||
const rightNode = sortedArrayToBST(mid + 1, right);
|
||
// 连接左右子树
|
||
curRoot.left = leftNode;
|
||
curRoot.right = rightNode;
|
||
return curRoot;
|
||
};
|
||
|
||
return sortedArrayToBST(0, inorder.length - 1);
|
||
}
|