栈(Stack)
定义
栈是一种特殊的线性表，特殊之处在于它只允许在表的一端进行添加和删除操作。
先进后出
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function Stack() {
this.data = new Array();
this.clear = function(){
this.data = new Array();
}
this.pop = function () {
return this.data.pop();
}
this.push = function (d) {
this.data.push(d);
}
this.getItem = function(){
return this.data[this.data.length-1];
}
}
|
应用
107.二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历)
例如：
给定二叉树 [3,9,20,null,null,15,7],
返回其自底向上的层次遍历为：
1
2
3
4
5
| [
[15,7],
[9,20],
[3]
]
|
实现
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
|
var levelOrderBottom = function (root) {
let DepthNode = function (node, depth) {
this.node = node;
this.depth = depth
}
let stack = [];
let answer = [];
if (root !== null) {
let node = stack.push(new DepthNode(root, 0));
while (stack.length) {
let node = stack.pop();
if (!Array.isArray(answer[node.depth])) {
answer[node.depth] = new Array();
}
answer[node.depth].push(node.node.val);
if (node.node.right) {
stack.push(new DepthNode(node.node.right, node.depth + 1));
}
if (node.node.left) {
stack.push(new DepthNode(node.node.left, node.depth + 1));
}
}
return answer.reverse();
} else {
return [];
}
};
|