折叠何宝莹

你会翻转二叉搜索树吗?(JS为例)invert binary tree

举个简单例子. 上图就是一个二叉搜索树.
实现的代码:

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
class Tree {
constructor(element=null) {
this.element = element
this.left = null
this.right = null
}

traversal() {
console.log('element is', this.element)
if (this.left !== null) {
this.left.traversal()
}
if (this.right !== null) {
this.right.traversal()
}
}
}

const testInvert = () => {
const a = new Tree('a')
const b = new Tree('b')
const c = new Tree('c')
const d = new Tree('d')
const e = new Tree('e')
const f = new Tree('f')
const g = new Tree('g')

a.left = b
a.right = c
b.left = d
b.right = e
c.left = f
c.right = g

a.traversal()
}

if (require.main === module) {
testInvert()
}

翻转后是怎样的呢?

这个题考量的是递归.

直接给答案吧.

1
2
3
4
5
6
7
8
9
const invert = (tree) => {
[tree.left, tree.right] = [tree.right, tree.left]
if (tree.left !== null) {
invert(tree.left)
}
if (tree.right !== null) {
invert(tree.right)
}
}

挺简单的.