leetcode105：从前序与中序遍历序列构造二叉树

题目链接

leetcode

题目描述

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

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
// 105. 从前序与中序遍历序列构造二叉树

#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 = -101;

// 辅助函数：创建二叉树
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;
}

/*
    递归构造：
		使用前序遍历的第一个节点作为根节点。
		在中序遍历中找到根节点的位置，从而确定左子树和右子树的范围。
		递归地构造左子树和右子树。

    时间复杂度：O(n)
        其中 n 是树中的结点个数。
        每次递归中，需要在中序遍历中查找根节点的位置，时间复杂度为 O(n)。
        由于递归调用的深度为树的高度，总时间复杂度为 O(n^2)。
        使用哈希表存储中序遍历中每个值的索引，查找根节点的时间复杂度可以优化到 O(1)。
        优化后，总时间复杂度为 O(n)。
    空间复杂度：O(n)
        递归调用的深度为树的高度，
        最坏情况下（树完全不平衡）为 O(n)，最好情况下（树完全平衡）为 O(log n)。
        使用哈希表存储中序遍历的索引，额外空间复杂度为 O(n)。
*/
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i ++) {
            pos[inorder[i]] = i;
        }
        return build(preorder, 0, preorder.size()-1,
            inorder, 0, inorder.size()-1);
    }
    
    /*
        前序遍历数组为 preorder[pl, pr]
        中序遍历数组为 inorder[il, ir]
        构造这个二叉树并返回该二叉树的根结点
    */
    TreeNode* build(vector<int>& preorder, int pl, int pr,
                    vector<int>& inorder, int il, int ir) {
        if (pl > pr || il > ir) return nullptr;

        TreeNode* root = new TreeNode(preorder[pl]);
        int inRoot = pos[root->val];
        root->left  = build(preorder, pl+1, pl+inRoot-il, inorder, il, inRoot-1);
        root->right = build(preorder, pl+inRoot-il+1, pr, inorder, inRoot+1, ir);
        return root;
    }

private:
    unordered_map<int, int> pos;
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> preorder = {3, 9, 20, 15, 7};
    vector<int> inorder = {9, 3, 15, 20, 7};

    // 构建二叉树
    TreeNode* root = solution.buildTree(preorder, inorder);
    // 打印二叉树
    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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
// 105. 从前序与中序遍历序列构造二叉树

package main

import (
	"fmt"
)

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

// printTree 打印二叉树的层序遍历结果
func printTree(root *TreeNode) string {
	if root == nil {
		return "[]"
	}

	var result []int
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		if node == nil {
			result = append(result, -1)
			continue
		}

		result = append(result, node.Val)
		queue = append(queue, node.Left, node.Right)
	}

	// 去掉尾部的空节点（仅当它们是连续的）
	for len(result) > 1 && result[len(result)-1] == -1 {
		result = result[:len(result)-1]
	}

	return fmt.Sprintf("%v", result)
}

/*
	递归构造：
		使用前序遍历的第一个节点作为根节点。
		在中序遍历中找到根节点的位置，从而确定左子树和右子树的范围。
		递归地构造左子树和右子树。

    时间复杂度：O(n^2)
        其中 n 是树中的结点个数。
        每次递归中，需要在中序遍历中查找根节点的位置，时间复杂度为 O(n)。
        由于递归调用的深度为树的高度，总时间复杂度为 O(n^2)。
    空间复杂度：O(n)
        递归调用的深度为树的高度，
        最坏情况下（树完全不平衡）为 O(n)，最好情况下（树完全平衡）为 O(log n)。
        使用哈希表存储中序遍历的索引，额外空间复杂度为 O(n)。
*/
// 从前序与中序遍历序列构造二叉树
func buildTree_0(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 || len(inorder) == 0 {
        return nil
    }

    // 前序遍历的第一个节点是根节点
	rootVal := preorder[0]
    root := &TreeNode{Val: rootVal}
    // 在中序遍历中找到根节点的位置
    index := findIndex(inorder, rootVal)

	// 递归构建左子树和右子树
	// 左子树的前序遍历范围是 preorder[1:1+rootIndex]
	// 左子树的中序遍历范围是 inorder[:rootIndex]
	// 右子树的前序遍历范围是 preorder[1+rootIndex:]
	// 右子树的中序遍历范围是 inorder[rootIndex+1:]
    root.Left  = buildTree(preorder[1:index+1], inorder[:index])
    root.Right = buildTree(preorder[index+1:], inorder[index+1:])
    return root
}

func findIndex(nums []int, target int) int {
    for i, v :=  range nums {
        if v == target {
            return i
        }
    }
    return -1
}

/*
	优化时间：使用哈希表存储中序遍历中每个值的索引

	时间复杂度：O(n)
		使用哈希表存储中序遍历中每个值的索引，查找根节点的时间复杂度可以优化到 O(1)。
		优化后，总时间复杂度为 O(n)。
    空间复杂度：O(n)
        递归调用的深度为树的高度，
        最坏情况下（树完全不平衡）为 O(n)，最好情况下（树完全平衡）为 O(log n)。
        使用哈希表存储中序遍历的索引，额外空间复杂度为 O(n)。
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 || len(inorder) == 0 {
        return nil
    }

    // 使用哈希表存储中序遍历的索引
	inorderIndex := make(map[int]int)
	for i, val := range inorder {
		inorderIndex[val] = i
	}

    var build func(preStart, preEnd, inStart, inEnd int) *TreeNode
	build = func(preStart, preEnd, inStart, inEnd int) *TreeNode {
		if preStart > preEnd {
			return nil
		}

		// 前序遍历的第一个节点是根节点
		rootVal := preorder[preStart]
		root := &TreeNode{Val: rootVal}
		// 在中序遍历中找到根节点的位置
		rootIndex := inorderIndex[rootVal]

		// 计算左子树的节点数量
		leftSize := rootIndex - inStart
		// 递归构建左子树
		root.Left = build(preStart+1, preStart+leftSize, inStart, rootIndex-1)
		// 递归构建右子树
		root.Right = build(preStart+leftSize+1, preEnd, rootIndex+1, inEnd)

		return root
	}

    return build(0, len(preorder)-1, 0, len(inorder)-1)
}

func main() {
	// 测试用例
	testCases := []struct {
		preorder  []int
		inorder   []int
		expected  []int
	}{
		{
			preorder:  []int{3,9,20,15,7},
			inorder:   []int{9,3,15,20,7},
			expected:  []int{3,9,20,-1,-1,15,7},
		},
		{
			preorder:  []int{-1},
			inorder:   []int{-1},
			expected:  []int{-1},
		},
	}

	for i, tc := range testCases {
		root := buildTree(tc.preorder, tc.inorder)
		fmt.Printf("Test Case %d, Input: preorder = %v, inorder = %v\n", i+1, tc.preorder, tc.inorder)
        result := printTree(root)
        expectedStr := fmt.Sprintf("%v", tc.expected)

		if result == expectedStr {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, expectedStr)
		}
	}
}
#leetcode
leetcode105：从前序与中序遍历序列构造二叉树
https://lcf163.github.io/2024/03/31/leetcode105：从前序与中序遍历序列构造二叉树/
作者
乘风的小站
发布于
2024年3月31日
许可协议