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

客官°小女子只卖身不卖艺 2022-12-31 12:27 107阅读 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 条评论，107人围观）

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

相关阅读

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

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

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

相关 LeetCode | 1382. Balance a Binary Search Tree将二叉搜索树变平衡【Python】

> LeetCode 1382. Balance a Binary Search Tree将二叉搜索树变平衡【Medium】【Python】【二叉树】 Problem

迈不过友情╰/ 2023年07月15日 05:54/ 0 赞/ 47 阅读

相关【LeetCode 1382】将二叉搜索树变平衡

题目描述给你一棵二叉搜索树，请你返回一棵平衡后的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1

今天药忘吃喽~/ 2023年02月23日 08:12/ 0 赞/ 4 阅读

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

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

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

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

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

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

相关 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 赞/ 167 阅读

相关 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 赞/ 181 阅读

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

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

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

相关【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 赞/ 235 阅读

相关 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 赞/ 348 阅读