5179.将二叉搜索树变平衡 (Medium)*

题目描述*

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

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

如果有多种构造方法，请你返回任意一种。

提示*

树节点的数目在 1 到 10^4 之间。树节点的值互不相同，且在 1 到 10^5 之间。

代码*

树的题还是挺熟的，这个就先中序遍历然后递归建树就行了。

class Solution {
private:
    TreeNode* build(vector<int>& inorder, int start, int end) {
        if(start > end) {
            return nullptr;
        }
        int mid = start + (end - start) / 2;
        auto root = new TreeNode(inorder[mid]);
        root->left = build(inorder, start, mid - 1);
        root->right = build(inorder, mid + 1, end);
        return root;
    }
public:
    TreeNode* balanceBST(TreeNode* root) {
        vector<int> inorder;
        stack<TreeNode*> s;
        auto cur = root;
        while(cur != nullptr || !s.empty()) {
            while(cur != nullptr) {
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top();
            s.pop();
            inorder.push_back(cur->val);
            cur = cur->right;
        }
        return build(inorder, 0, inorder.size() - 1);
    }
};

最后更新: July 23, 2022