Given a binary search tree, return a balanced binary search tree with the same node values.
A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.
If there is more than one answer, return any of them.
Example 1:
Input: root = [1,null,2,null,3,null,4,null,null] Output: [2,1,3,null,null,null,4] Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.
Constraints:
- The number of nodes in the tree is between
1
and10^4
. - The tree nodes will have distinct values between
1
and10^5
.
Solution: Inorder + recursion
Use inorder traversal to collect a sorted array from BST. And then build a balanced BST from this sorted array in O(n) time.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: TreeNode* balanceBST(TreeNode* root) { vector<int> vals; function<void(TreeNode*)> inorder = [&](TreeNode* root) { if (!root) return; inorder(root->left); vals.push_back(root->val); inorder(root->right); }; function<TreeNode*(int, int)> build = [&](int l, int r) { if (l > r) return (TreeNode*)nullptr; int m = l + (r - l) / 2; auto root = new TreeNode(vals[m]); root->left = build(l, m - 1); root->right = build(m + 1, r); return root; }; inorder(root); return build(0, vals.size() - 1); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment