前言
仅记录自己敲过的题，留个爪印。
注意：二叉树问题，基本要考虑是否采用递归
二叉树翻转
二叉树翻转为左子树和右子树翻转位置
1
2
3
4
5
6
7
8
9
10
11
| const reverse = function (root) {
if (!root) return root;
const left = reverse(root.left);
const right = reverse(root.right);
root.right = left;
root.left = right;
return root;
}
|
二叉搜索树
什么是二叉搜索树？
二叉搜索树（又：二叉搜索树，二叉排序树），一棵二叉搜索树有如下性质：
- 是一棵空树
- 是一棵由根结点、左子树、右子树组成的树，
- 同时左子树和右子树都是二叉搜索树，
- 且左子树上所有结点的数据域都小于等于根结点的数据域，右子树上所有结点的数据域都大于等于根结点的数据域
例如：
8
/ \
5 9
/ \ \
4 6 10
关于二叉搜索树高频操作：
- 查找数据域为某一特定值的结点
- 插入新结点
- 删除指定结点
查找节点
题：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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| const root1 = {
val: 8,
left: {
val: 6,
left: {
val: 5
},
right: {
val: 7
}
},
right: {
val: 9,
right: {
val: 10
}
}
};
const search = function (data, root) {
if (!data || !root) return null;
if (root.val === data) {
console.log('目标结点是：', root)
} else if (data < root.val) {
search(data, root.left)
} else if (data > root.val) {
search(data, root.right)
}
}
|
插入新结点
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
|
const root2 = {
val: 9,
left: {
val: 5,
left: {
val: 3
},
right: {
val: 7
}
},
right: {
val: 10,
right: {
val: 12
}
}
};
function TreeNode(val, left, right) {
this.val = (val === undefined ? 0 : val)
this.left = (left === undefined ? null : left)
this.right = (right === undefined ? null : right)
}
const insert = function (data, root) {
if (!data) return
if (!root) {
root = new TreeNode(data)
return root
}
if (root.val > data) {
root.left = insert(data, root.left)
}
if (root.val < data) {
root.right = insert(data, root.right)
}
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
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
| const root3 = {
val: 9,
left: {
val: 5,
left: {
val: 3
},
right: {
val: 7
}
},
right: {
val: 11,
left: {
val: 10
},
right: {
val: 12
}
}
};
function deleteNode(val, root) {
if (!root) return root;
if (root.val === val) {
if (root.left) {
const maxNode = findMax(root.left)
root.val = maxNode.val;
root.left = deleteNode(maxNode.val, root.left)
} else if (root.right) {
const minNode = findMin(root.right);
root.val = minNode.val;
root.right = deleteNode(minNode.val, root.right);
} else if (!root.right && !root.left) {
root = null
}
} else if (val > root.val) {
root.right = deleteNode(val, root.right);
} else if (val < root.val) {
root.left = deleteNode(val, root.left);
}
return root
}
function findMax(root) {
while (root.right) {
root = root.right
}
return root
}
function findMin(root) {
while (root.left) {
root = root.left
}
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
| const root4 = {
val: 9,
left: {
val: 5,
left: {
val: 4
},
right: {
val: 7
}
},
right: {
val: 8,
left: {
val: 10
},
right: {
val: 1
}
}
};
const isValidBST = function (root) {
if (!root) return true
if ((root.right && root.right.val < root.val) || (root.left && root.left.val > root.val)) return false
return isValidBST(root.right) && isValidBST(root.left)
}
|
对特性的考察：将排序数组转化为二叉搜索树
题目描述：将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树
给定有序数组: [-10,-3,0,5,9]
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
|
const sortedArrayToBST = function (nums) {
if (!(nums && nums.length)) return new TreeNode();
const len = nums.length
let root = buildBST(0, len - 1);
function buildBST(startIndex, endIndex) {
if (startIndex > endIndex) return null
let mid = Math.floor((startIndex + (endIndex - startIndex) / 2));
let cur = new TreeNode(nums[mid])
cur.left = buildBST(startIndex, mid - 1)
cur.right = buildBST(mid + 1, endIndex)
return cur
}
return root
};
|
