【经典算法】LeetCode 108. 将有序数组转换为二叉搜索树(Java/C/Python3/Go实现含注释说明,Easy)

• 标签(题目类型)：树，二叉搜索树，数组

题目描述

给定一个有序整数数组，将其转换为一棵高度平衡的二叉搜索树。

原题：LeetCode 108. 将有序数组转换为二叉搜索树

思路及实现

方式一：递归中值法

思路

我们可以使用递归的方法来构建二叉搜索树。每次递归，我们选择数组的中间元素作为根节点，然后将数组分为左右两部分，分别构建左子树和右子树。

代码实现

Java版本

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return buildBST(nums, 0, nums.length - 1);
    }

    private TreeNode buildBST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildBST(nums, start, mid - 1);
        root.right = buildBST(nums, mid + 1, end);
        
        return root;
    }
}
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

说明：

• TreeNode 是树节点的定义。
• sortedArrayToBST 方法是入口点，首先检查输入数组的有效性，然后调用 buildBST 方法进行递归构建。
• buildBST 方法是递归构建二叉搜索树的核心。它首先找到中间索引 mid，然后创建根节点，并递归地为左半部分和右半部分构建子树。

C语言版本

#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* buildBST(int* nums, int start, int end) {
    if (start > end) {
        return NULL;
    }
    
    int mid = (start + end) / 2;
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = nums[mid];
    root->left = buildBST(nums, start, mid - 1);
    root->right = buildBST(nums, mid + 1, end);
    
    return root;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize){
    if (nums == NULL || numsSize == 0) {
        return NULL;
    }
    return buildBST(nums, 0, numsSize - 1);
}
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

说明：

• 这里使用 C 语言标准库中的 malloc 来动态分配内存。
• 其余逻辑与 Java 版本类似。

Python3版本

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        
        def buildBST(start, end):
            if start > end:
                return None
            
            mid = (start + end) // 2
            root = TreeNode(nums[mid])
            root.left = buildBST(start, mid - 1)
            root.right = buildBST(mid + 1, end)
            
            return root
        
        return buildBST(0, len(nums) - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

说明：

• 使用 Python 类来定义树节点。
• sortedArrayToBST 方法是入口点，它定义了一个内部递归函数 buildBST 来构建二叉搜索树。

Golang版本

package main

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right*TreeNode
}

func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    
    return buildBST(nums, 0, len(nums)-1)
}

func buildBST(nums []int, start, end int) *TreeNode {
    if start > end {
        return nil
    }
    
    mid := (start + end) / 2
    root := &TreeNode{Val: nums[mid]}
    root.Left = buildBST(nums, start, mid-1)
    root.Right = buildBST(nums, mid+1, end)
    
    return root
}

func main() {
    // 示例用法
    nums := []int{-10, -3, 0, 5, 9}
    root := sortedArrayToBST(nums)
    // 这里可以添加遍历树的代码来验证结果
}
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

说明：

• 使用 Go 语言的结构体来定义树节点。
• sortedArrayToBST 方法是入口点，调用 buildBST 方法来构建二叉搜索树。
• buildBST 方法是递归函数，用于构建二叉搜索树。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。每个元素只被访问和处理一次。
• 空间复杂度：O(log n)，平均情况下。递归调用栈的深度取决于树的高度，而平衡二叉搜索树的高度是 log n（以 2 为底）。在最坏的情况下（当输入数组已经排序并且完全不平衡时，例如数组中没有重复元素且递增或递减），空间复杂度会退化到 O(n)。但由于题目要求转换为高度平衡的二叉搜索树，因此平均情况下是 O(log n)。

方式二：迭代法

思路

1. 初始化一个空栈，并确定数组的中点作为根节点。
2. 将根节点压入栈中，并标记为已处理（如果需要的话）。
3. 创建一个循环，直到栈为空：
   • 弹出栈顶节点，并处理其左子树（如果存在）：
     • 找到左子树的起始索引和结束索引。
     • 计算左子树的中点，并创建新的左子节点。
     • 将左子节点设置为当前弹出节点的左孩子。
     • 如果左子树非空，将左子节点压入栈中。
   • 处理当前节点的右子树（如果存在）：
     • 找到右子树的起始索引和结束索引。
     • 计算右子树的中点，并创建新的右子节点。
     • 将右子节点设置为当前弹出节点的右孩子。
     • 如果右子树非空，将右子节点压入栈中。
4. 当栈为空时，表示所有的节点都已经处理完毕，BST构建完成。

代码实现

迭代法构建二叉搜索树（BST）通常不如递归方法直观，但可以通过维护一个栈来模拟递归过程。以下是迭代法构建BST的思路以及使用Python、Java、C++和JavaScript四种语言的实现，包括注释和代码说明。

Java实现

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) return null;

        Deque<Object[]> stack = new ArrayDeque<>();
        int start = 0, end = nums.length - 1;
        TreeNode root = new TreeNode(nums[(start + end) / 2]);
        stack.push(new Object[]{root, start, end});

        while (!stack.isEmpty()) {
            Object[] curr = stack.poll();
            TreeNode node = (TreeNode) curr[0];
            int s = (int) curr[1], e = (int) curr[2];
            int mid = s + (e - s) / 2;

            if (s < mid) {
                TreeNode leftChild = new TreeNode(nums[mid - 1]);
                node.left = leftChild;
                stack.push(new Object[]{leftChild, s, mid - 1});
            }

            if (mid + 1 < e) {
                TreeNode rightChild = new TreeNode(nums[mid + 1]);
                node.right = rightChild;
                stack.push(new Object[]{rightChild, mid + 1, e});
            }
        }

        return root;
    }
}
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

Python实现

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sortedArrayToBST(nums):
    if not nums:
        return None

    stack, start, end = [], 0, len(nums) - 1
    root = TreeNode(nums[start + (end - start) // 2])
    stack.append((root, start, end))

    while stack:
        node, start, end = stack.pop()
        mid = (start + end) // 2

        if start < mid:
            left_child = TreeNode(nums[mid - 1])  # 左子树的根（实际上是mid-1，因为mid是根）
            node.left = left_child
            stack.append((left_child, start, mid - 1))

        if mid + 1 < end:
            right_child = TreeNode(nums[mid + 1])  # 右子树的根（实际上是mid+1）
            node.right = right_child
            stack.append((right_child, mid + 1, end))

    return root

# 示例
nums = [-10, -3, 0, 5, 9]
root = sortedArrayToBST(nums)
# 遍历BST的代码略
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

C++实现

#include <stack>
#include <vector>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* sortedArrayToBST(std::vector<int>& nums) {
    if (nums.empty()) {
        return nullptr;
    }

    std::stack<std::pair<TreeNode*, std::pair<int, int>>> stk;
    int n = nums.size();
    TreeNode* root = new TreeNode(nums[n / 2]);
    stk.push({root, {0, n - 1}});

    while (!stk.empty()) {
        auto curr = stk.top();
        stk.pop();

        TreeNode* node = curr.first;
        int start = curr.second.first;
        int end = curr.second.second;
        int mid = start + (end - start) / 2;

        if (start < mid) {
            node->left = new TreeNode(nums[mid - 1]); // 左子树的根节点
            stk.push({node->left, {start, mid - 1}});
        }

        if (mid + 1 < end) {
            node->right = new TreeNode(nums[mid + 1]); // 右子树的根节点
            stk.push({node->right, {mid + 1, end}});
        }
    }

    return root;
}

// 示例用法
int main() {
    std::vector<int> nums = {-10, -3, 0, 5, 9};
    TreeNode* root = sortedArrayToBST(nums);
    // 遍历BST的代码略

    return 0;
}
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

Go版本

当然，以下是Go语言版本的实现，其中包含了代码注释和说明：

package main

import (
	"fmt"
)

// TreeNode represents a node in a binary tree
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// sortedArrayToBST converts a sorted array to a balanced binary search tree
func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}

	// 定义辅助函数来构建BST
	var helper func(start, end int) *TreeNode
	helper = func(start, end int) *TreeNode {
		if start > end {
			return nil
		}

		// 找到中间元素作为当前子树的根
		mid := (start + end) / 2
		root := &TreeNode{Val: nums[mid]}

		// 递归地构建左子树和右子树
		root.Left = helper(start, mid-1)
		root.Right = helper(mid+1, end)

		return root
	}

	// 调用辅助函数从整个数组构建BST
	return helper(0, len(nums)-1)
}

// inorderTraversal performs in-order traversal of a binary tree
func inorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}

	inorderTraversal(root.Left)
	fmt.Println(root.Val)
	inorderTraversal(root.Right)
}

func main() {
	nums := []int{-10, -3, 0, 5, 9}
	root := sortedArrayToBST(nums)

	// 验证BST是否构建正确，进行中序遍历
	inorderTraversal(root)
}
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

代码说明：

1. TreeNode 结构体定义了一个二叉树的节点，包含一个整数值Val和两个指向左右子节点的指针Left和Right。

2. sortedArrayToBST 函数接受一个排序数组nums，并返回一个指向平衡二叉搜索树根的指针。该函数定义了一个内部辅助函数helper，它递归地构建BST。

3. 在helper函数中，我们首先检查start是否大于end，如果是，则返回nil表示没有节点可构建。然后，我们找到中间元素mid作为当前子树的根，并创建对应的TreeNode。接下来，我们递归地调用helper来构建左子树和右子树，并将返回的根节点分别赋值给当前节点的Left和Right。

4. inorderTraversal 函数用于验证BST是否构建正确。它使用中序遍历的方式遍历BST，并打印出每个节点的值。由于BST的性质，中序遍历将得到一个升序的序列。

5. 在main函数中，我们创建了一个排序数组nums，并调用sortedArrayToBST来构建BST。然后，我们调用inorderTraversal来遍历BST并打印其节点值。

复杂度分析

对于上述四种语言的实现，它们的复杂度分析是相同的：

• 时间复杂度：O(n)，其中n是数组的长度。每个元素只被访问和处理一次。
• 空间复杂度：O(log n)，平均情况下。这是因为栈的深度取决于BST的高度，对于平衡BST来说，其高度是O(log n)。然而，在最坏的情况下（当输入数组已经排序并且完全不平衡时），空间复杂度会退化到O(n)。但在这个问题中，我们总是从数组的中点开始构建BST，因此通常能得到一个相对平衡的BST，使得空间复杂度保持在O(log n)的平均水平。

总结

总结

以下是对于两种构建平衡二叉搜索树（BST）的方式的总结，包括它们的优点、缺点、时间复杂度和空间复杂度，以及其他特点：

说明：

• 递归中值法：该方法直接通过递归找到数组的中值作为根节点，然后递归地构建左子树和右子树。这种方法逻辑清晰，易于理解，但在最坏情况下（如数组已排序），递归调用栈可能会占用大量的空间。
• 迭代栈方法：该方法使用栈来模拟递归过程，避免了递归调用栈的空间占用问题。但相比递归方法，代码可能略显复杂。在处理大数据集时，迭代栈方法通常更加节省空间。
• 时间复杂度：对于两种方法，时间复杂度都是 O(n)，因为每个元素都需要被处理一次。
• 空间复杂度：对于递归中值法，空间复杂度取决于递归调用栈的深度，平均情况下为 O(log n)，但在最坏情况下（如数组已排序）为 O(n)。对于迭代栈方法，空间复杂度同样是平均 O(log n)，最坏 O(n)，因为栈可能需要存储所有节点。但在实际应用中，迭代栈方法通常更加节省空间。
• 其他：两种方法各有特点，递归中值法更易于理解和实现，而迭代栈方法更节省空间。在选择使用哪种方法时，需要根据具体的应用场景和需求来权衡。

相似题目