二叉树
二叉树:即每个节点最多有两个子树的树状结构
二叉查找树,二叉排序树,二叉搜索树:左节点<根节点<右节点的数据结构
基本二叉树的构造函数
function Node(val) {
this.left = this.right = null
this.val = val
}
1
2
3
4
2
3
4
模拟二叉树数据(node1是根节点)
var node4 = {left: null, right: null, val: 4 };
var node5 = {left: null, right: null, val: 5 };
var node6 = {left: null, right: null, val: 6 };
var node7 = {left: null, right: null, val: 7 };
var node3 = {left: node6, right: node7, val: 3 };
var node2 = {left: node4, right: node5, val: 2 };
var node1 = {left: node2, right: node3, val: 1 };
实际结构如下:
// 1
// /\
// 2 3
// /\ /\
// 4 5 6 7
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
1.前序遍历
递归实现
function qianxubianli(node) {
if(!node) {
return
}
console.log(node.val)
node.left&&qianxubianli(node.left)
node.right&&qianxubianli(node.right)
}
qianxubianli(node1)
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
迭代实现
function qianxubianli(node) {
var stack = [];
var result = [];
stack.push(node);
while(stack.length) {
var item = stack.pop();
result.push(item.val);
if(item.right) {
stack.push(item.right)
}
if(item.left) {
stack.push(item.left);
}
}
console.log(result)
}
qianxubianli(node1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2.中序遍历
递归实现
function zhongxubianli(node) {
if(!node) {
return
}
node.left && zhongxubianli(node.left)
console.log(node.val)
node.right && zhongxubianli(node.right)
}
zhongxubianli(node1)
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
迭代实现
function zhongxubainli(node) {
var stack = [];
var result = [];
stack.push(node);
while(stack.length) {
var item = stack[stack.length-1];
if(item.left && !item.left.isOK) {
stack.push(item.left)
} else if(!item.left || item.left && item.left.isOK) {
var index = stack.pop();
result.push(index.val);
index.isOK = true;
item.right && stack.push(item.right);
}
}
console.log(result)
}
zhongxubainli(node1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
3.后序遍历
递归实现
function houxubianli(node) {
if(!node) {
return
}
node.left && houxubianli(node.left)
node.right && houxubianli(node.right)
console.log(node.val)
}
houxubianli(node1)
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
迭代实现
function houxubianli(node) {
var stack = [];
var result = [];
stack.push(node);
while(stack.length) {
var item = stack[stack.length-1];
if(item.left && !item.left.isOK) {
stack.push(item.left)
} else if(item.right && !item.right.isOK) {
stack.push(item.right)
// 如果是叶子节点，或者子节点都输出了，则可以弹出该节点
} else if((!item.left || item.left && item.left.isOK) && (!item.right || item.right && item.right.isOK)) {
var index = stack.pop();
result.push(index.val);
index.isOK = true;
}
}
console.log(result)
}
houxubianli(node1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
4.层次遍历
function cengcibianli(node) {
var queue = [];
var result = [];
queue.push(node);
while (queue.length) {
for (let i = 0; i < queue.length; i++) {
var item = queue.shift();
result.push(item.val);
item.left && queue.push(item.left);
item.right && queue.push(item.right);
}
}
console.log(result)
}
cengcibianli(node1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5.剑指Offer
重建二叉树：给出前序和中序遍历重建这个二叉树，通过前序遍历获取根节点然后通过递归，找到前序遍历的左子树和中序遍历的左子树递归遍历（终止条件：左子树长度为0返回NULL），右子树相同。
二叉树镜像：利用前序遍历先获取根节点然后获取子节点进行替换，然后递归遍历左节点和右节点即可（当节点为NULL则返回即可）。
从上往下打印二叉树：对二叉树进行层次遍历即可。
二叉树中和为某一个值的路径：对二叉树进行前序遍历，并把路径作为函数参数传入，若该节点的值为传入参数值且是叶子节点，则推入结果数组中。
function findQuickPath(root, result, path, num) {
// 判断条件为节点值相同并且是叶子节点
if(root.val === num && root.right === null && root.left === null) {
result.push(path)
}
let myNum = num - root.val;
path.push(root.val);
if(root.left) {
// 使用浅拷贝保证数组不被修改
findQuickPath(root.left, result, path.slice(0), myNum)
}
if(root.right) {
findQuickPath(root.right, result, path.slice(0), myNum)
}
return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
二叉树的深度：使用递归，注意返回值即可。层次遍历每到一层深度加1即可
function TreeDepth(pRoot) {
if (!pRoot) {
return 0
}
return Math.max(1 + TreeDepth(pRoot.left), 1 + TreeDepth(pRoot.right))
}
// 非递归
function TreeDepth(pRoot) {
if (!pRoot) {
return 0
}
var depth = 0;
var queue = [pRoot];
while(queue.length) {
depth++;
for(let i = 0; i < queue.length; i++) {
let item = queue.shift();
item.left && queue.push(item.left);
item.right && queue.push(item.right);
}
}
return depth
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
平衡二叉树：先求出左右节点的二叉树高度，如果相差小于1，则递归遍历左右子节点即可。可采用后序遍历减少比较的开销：
function isBalance(node) {
return getDepth(node) !== -1;
function getDepth(node) {
if (node === null) return 0;
let left = getDepth(node.left);
if (left === -1) return -1;
let right = getDepth(node.right);
if (right === -1) return -1;
return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
二叉树中序遍历的下一个节点：每个节点有一个next指针指向父节点
1、有右子树的，那么下个结点就是右子树最左边的点；
2、没有右子树的，也可以分成两类，a)是父节点左孩子 ，那么父节点就是下一个节点 ； b)是父节点的右孩子找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有，那么他就是尾节点。
function GetNext(pNode) {
if (!pNode) {
return null
}
var result = null;
// 有右子树的，那么下个结点就是右子树最左边的点
if (pNode.right) {
result = pNode.right;
while (result.left) {
result = result.left;
}
} else {
// 没有右子树且是父节点右孩子
if (pNode.next && pNode.next.right === pNode) {
result = pNode.next;
// 一直找其父节点
while (result.next && result.next.right === result) {
result = result.next;
}
// 如果父节点为空，则返回空，不为空则代表当前节点是父节点的左节点则直接返回父节点
if (result.next === null) {
return null
} else {
result = result.next;
}
} else {
// 没有右子树且是父节点左孩子
result = pNode.next;
}
}
return result
}
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
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
二叉树对称：通过递归判断每个节点的值是否都是null或者相等，null则返回true，相等则判断其左右节点的值是否相等。采用队列保存节点的左右节点，然后入队和出队都是成对出现，并进行判断即可。
function isSymmetrical(pRoot) {
if(pRoot === null) {
return true
}
var queue = [];
queue.push(pRoot.left);
queue.push(pRoot.right);
while(queue.length) {
var left = queue.shift();
var right = queue.shift();
if(left === null && right === null) continue;
if(left === null || right === null) return false;
if(left.val !== right.val) return false;
queue.push(left.left);
queue.push(right.right);
queue.push(left.right);
queue.push(right.left);
}
return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
之字形打印二叉树：层次遍历并用变量判断输出即可。
二叉树序列化和反序列化：采用递归做法很简单（每个空节点则打印#来表示）
function Serialize(pRoot) {
var stack = [];
var str = [];
stack.push(pRoot);
while (stack.length) {
let item = stack.pop();
if (!item) {
str.push('$');
continue;
}
str.push(item.val);
stack.push(item.right);
stack.push(item.left);
}
return str
}
function Deserialize(str) {
if(str.length <= 1) {
return null
}
var root = null;
var temp = str.shift();
if(typeof temp === 'number'){
root = new TreeNode(temp);
root.left = Deserialize(str);
root.right = Deserialize(str);
}
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
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
采用层次遍历：
function Serialize(pRoot) {
var queue = [];
queue.push(pRoot);
var str = [];
while (queue.length) {
let item = queue.shift();
if (item === null) {
str.push('#');
continue;
}
str.push(item.val);
queue.push(item.left);
queue.push(item.right);
}
return str.join(', ')
}
function Deserialize(str) {
var arr = str.split(', ');
var newarr = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] === '#') {
newarr.push(null);
} else {
newarr.push(new TreeNode(arr[i]));
}
}
for (let i = 0, j = 1; j < newarr.length; i++) {
if (newarr[i] !== null) {
newarr[i].left = newarr[j++];
newarr[i].right = newarr[j++];
}
}
return newarr[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
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
采用前序遍历（反序列化逻辑有些难懂）：
function Serialize(pRoot) {
var stack = [];
var str = [];
stack.push(pRoot);
while (stack.length) {
let item = stack.pop();
if (!item) {
str.push('#')
continue;
}
str.push(item.val);
stack.push(item.right);
stack.push(item.left);
}
return str.join(', ')
}
function Deserialize(str) {
if (str.length <= 1) {
return null
}
var arr = str.split(', ');
var stack = [];
var newarr = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== '#') {
newarr[i] = new TreeNode(arr[i]);
} else {
newarr[i] = null;
}
}
var root = newarr[0];
stack.push(newarr[0]);
let i = 1;
while (newarr[i] !== null) {
let len = stack.length;
stack[len - 1].left = newarr[i];
stack.push(newarr[i++]);
}
while (stack.length) {
stack.pop().right = newarr[++i];
if (newarr[i] !== null) {
stack.push(newarr[i++]);
while (newarr[i] !== null) {
let len = stack.length;
stack[len - 1].left = newarr[i];
stack.push(newarr[i++]);
}
}
}
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
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
总结
- 二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。
- 深度优先对每一个可能的分支路径深入到不能再深入为止,先序遍历、中序遍历、后序遍历属于深度优先。
- 广度优先又叫层次遍历，从上往下，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。