Balance a Binary Search Tree（C++将二叉搜索树变平衡）

客官°小女子只卖身不卖艺 2022-12-31 12:27 91阅读 0赞

解题思路：

（1）先求出递增的序列

（2）递归构建平衡二叉树

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        void inorder(vector<int> &v,TreeNode *root) {
            if(root==NULL) return;
            inorder(v,root->left);
            v.push_back(root->val);
            inorder(v,root->right);
        }
        
        TreeNode* create_node(vector<int> &v) {
            if(v.size()==0) return NULL;
            int mid=(v.size()-1)/2;
            TreeNode *root = new TreeNode(v[mid]);
            
            vector<int> v1,v2;
            for(int i=0;i<v.size();i++) {
                if(i<mid) v1.push_back(v[i]);
                else if(i>mid) v2.push_back(v[i]);
            }
            root->left=create_node(v1);
            root->right=create_node(v2);
            
            return root;
        }
        
        TreeNode* balanceBST(TreeNode* root) {
            vector<int> v;
            inorder(v,root);
            return create_node(v);
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，91人围观）

还没有评论，来说两句吧...

相关阅读

相关平衡二叉树（Self-balancing binary search tree）之AVL树

1.基础（基础）二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），也称二叉搜索树 2.AVL树出现的背景（AVL

傷城~/ 2023年07月22日 03:47/ 0 赞/ 51 阅读

相关 Balance a Binary Search Tree（C++将二叉搜索树变平衡）

解题思路：（1）先求出递增的序列（2）递归构建平衡二叉树 / Definition for a binary tree node. s

客官°小女子只卖身不卖艺/ 2022年12月31日 12:27/ 0 赞/ 92 阅读

相关二叉搜索树（binary search tree）

定义二叉搜索树：二叉树中任何节点的键值一定大于其左子树中每一个节点的键值，并且小于其右子树中每一个节点的键值。查找基于此，在二叉搜索树中搜索最小元素和最大元

电玩女神/ 2022年08月08日 14:39/ 0 赞/ 151 阅读

相关 Glib学习（9）平衡二叉树 Balanced Binary Trees

平衡二叉树（Balanced Binary Tree）又被称为AVL树且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵

水深无声/ 2022年07月24日 07:15/ 0 赞/ 131 阅读

相关 110. Balanced Binary Tree （平衡二叉树判断）

Given a binary tree, determine if it is height-balanced. For this problem, a height-bal

迈不过友情╰/ 2022年07月15日 01:18/ 0 赞/ 147 阅读

相关 110. Balanced Binary Tree （平衡二叉树判断）

Given a binary tree, determine if it is height-balanced. For this problem, a height-bal

港控/mmm°/ 2022年07月15日 01:18/ 0 赞/ 162 阅读

相关 [Leetcode][python]Balanced Binary Tree/平衡二叉树

题目大意判断一颗二叉树是否是“高度”平衡的。平衡二叉树的定义是二叉树的任意节点的两颗子树之间的高度差小于等于1。这实际上是[AVL树（维基百科）][AVL]

喜欢ヅ旅行/ 2022年06月11日 08:16/ 0 赞/ 171 阅读

相关 LeetCode 110.Balanced Binary Tree (平衡二叉树)

题目描述：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为： > 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例

小鱼儿/ 2022年05月09日 04:56/ 0 赞/ 151 阅读

相关【Leetcode】110. Balanced Binary Tree（平衡二叉树）

Given a binary tree, determine if it is height-balanced. For this problem, a height-bal

小灰灰/ 2022年02月17日 14:35/ 0 赞/ 208 阅读

相关 LeetCode : 110. Balanced Binary 平衡二叉树

试题 Given a binary tree, determine if it is height-balanced. For this problem, a heigh

一时失言乱红尘/ 2021年06月24日 16:10/ 0 赞/ 318 阅读