leetcode108：将有序数组转换为二叉搜索树

题目链接

leetcode

题目描述

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

// 二叉树结点的定义
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) {}
};

const int NULL_NODE = -10001;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    递归实现

    以中点为根，以左半部分为左子树，右半部分为右子树。
    分别构造左子树和右子树，然后令根结点的指针分别指向两棵子树。
    证明该算法构造的二叉树是 BST，满足条件：
        任意结点的左右子树中所有高度的差不大于 1。

    选择中间数字作为 BST 的根结点，这样分给左右子树的数字个数相同或相差 1，可以使得树保持平衡。
    如果数组长度是奇数，则根结点的选择是唯一的。
    如果数组长度是偶数，则可以选择中间位置（左边或右边）的数字作为根结点作为根结点。
    选择不同的数字作为根结点，创建的平衡二叉搜索树也是不同的。
    
    时间复杂度：O(n)
        其中 n 是数组的长度。每个结点都会被访问一次。
    空间复杂度：O(logn)
        取决于递归调用栈的深度。
        在平均情况下，树的高度为 O(logn)，所以空间复杂度为 O(logn)；
        在最坏情况下，树退化为链表，空间复杂度为 O(n)。
        但平均情况下，空间复杂度接近 O(logn)。
*/
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }

    TreeNode* build(vector<int>& nums, int l, int r) {
        if (l > r) return nullptr;

        // 根结点的选择，中间位置左边的数字
        int mid = (l + r) / 2;
        // 根结点的选择，中间位置右边的数字
        // int mid = (l + r + 1) / 2;
        // 根结点的选择，中间位置左边或右边的数字
        // int mid = (l + r + rand() % 2) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = build(nums, l, mid - 1);
        root->right = build(nums, mid + 1, r);
        
        return root;
    }
};

/*
    思路同上
*/
class Solution_1 {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return nullptr;

        // 根结点的选择，中间位置左边的数字
        int mid = nums.size() / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        vector<int> left(nums.begin(), nums.begin() + mid);
        vector<int> right(nums.begin() + mid + 1, nums.end());
        root->left = sortedArrayToBST(left);
        root->right = sortedArrayToBST(right);
        
        return root;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {-10, -3, 0, 5, 9};

    // 构建二叉搜索树
    TreeNode* root = solution.sortedArrayToBST(nums);

    // 打印结果
    levelOrderTraversal(root);

    // 释放内存
    deleteTree(root);

    return 0;
}

Golang 代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package main

import "fmt"

// 定义二叉树节点
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 创建二叉树
func createTree(values []int) *TreeNode {
	if len(values) == 0 {
		return nil
	}
	root := &TreeNode{Val: values[0]}
	queue := []*TreeNode{root}
	i := 1
	for i < len(values) {
		node := queue[0]
		queue = queue[1:]

		if i < len(values) && values[i] != -1 {
			node.Left = &TreeNode{Val: values[i]}
			queue = append(queue, node.Left)
		}
		i++

		if i < len(values) && values[i] != -1 {
			node.Right = &TreeNode{Val: values[i]}
			queue = append(queue, node.Right)
		}
		i++
	}
	return root
}

// 层序遍历二叉树
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	result := [][]int{}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		levelSize := len(queue)
		level := []int{}
		for i := 0; i < levelSize; i++ {
			node := queue[0]
			queue = queue[1:]
			level = append(level, node.Val)
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		result = append(result, level)
	}
	return result
}

/*
    基本思路：
        选取有序数组的中间元素作为二叉搜索树的根节点。
        将数组分为左右两部分，
        左边部分递归地构建根节点的左子树，右边部分递归地构建根节点的右子树。
    
    时间复杂度：O(n)
        其中 n 是数组的长度。每个节点都会被访问一次。
    空间复杂度：O(logn)
        取决于递归调用栈的深度。
        在平均情况下，树的高度为 O(logn)，所以空间复杂度为 O(logn)；
        在最坏情况下，树退化为链表，空间复杂度为 O(n)。
        但平均情况下，空间复杂度接近 O(logn)。
*/
// 将有序数组转换为二叉搜索树
func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }

    mid := len(nums) / 2
    root := &TreeNode{Val: nums[mid]}
    root.Left = sortedArrayToBST(nums[:mid])
    root.Right = sortedArrayToBST(nums[mid + 1:])
    return root
    // return &TreeNode{
    //     Val: nums[mid],
    //     Left: sortedArrayToBST(nums[:mid]),
    //     Right: sortedArrayToBST(nums[mid + 1:]),
    // }
}

func main() {
    // 测试用例
    testCases := []struct {
        nums     []int
        expected [][]int
    }{
        {
            nums:     []int{-10,-3,0,5,9},
            expected: [][]int{{0}, {-3,9}, {-10,5}},
        },
        {
            nums:     []int{1,3},
            expected: [][]int{{3}, {1}},
        },
    }

    for i, tc := range testCases {
        root := sortedArrayToBST(tc.nums)
		fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)
        result := levelOrder(root)
		resultStr := fmt.Sprintf("%v", result)
		expectedStr := fmt.Sprintf("%v", tc.expected)

        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}
#leetcode
leetcode108：将有序数组转换为二叉搜索树
https://lcf163.github.io/2024/03/31/leetcode108：将有序数组转换为二叉搜索树/
作者
乘风的小站
发布于
2024年3月31日
许可协议