深度优先遍历 DFS( Depth First Search )
- 前序遍历
根 -> 左子树 -> 右子树
-
递归
1
2
3
4
5
6function DFS1(root) {
if(!root) return null;
console.log(root.val);
DFS1(root.left);
DFS1(root.right);
} -
非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14function DFS2(root) {
if(!root) return null;
const st = [root];
while(st.length>0) {
const top = st.pop();
console.log(top.val);
if(st.rightChild) {
st.push(st.rightChild);
}
if(st.leftChild) {
st.push(st.leftChild);
}
}
}
- 中序遍历
左子树 -> 根 -> 右子树
-
递归
1
2
3
4
5
6function DFS3(root) {
if(!root) return null;
DFS3(root.leftChild);
console.log(root.val);
DFS3(root.rightChild);
} -
非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15function DFS4(root) {
if(!root) return null;
const st = [];
let cur = root;
while(cur || st.length > 0) {
if(cur) {
st.push(cur);
cur = cur.leftChild;
} else {
const top = st.pop();
console.log(top.val);
cur = top.rightChild;
}
}
}
- 后序遍历
左子树 -> 右子树 -> 根
-
递归
1
2
3
4
5
6function DFS5(root) {
if(!root) return null;
DFS5(root.leftChild);
DFS5(root.rightChild);
console.log(root.val);
} -
非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20function DFS6(root) {
if(!root) return null;
const st = [];
let cur = root;
while(cur || st.length) {
if(cur) {
st.push(cur);
cur = st.leftChild;
} else {
const top = st.pop();
if(top.visit) {
console.log(top.val);
cur = null;
} else {
st.push(top);
cur = top.rightChild;
}
}
}
}
广度优先遍历 BFS( Breadth First Search )
即层次遍历
- 非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14function BFS1 (root) {
if(!root) return null;
const q = [root];
while(q.length > 0) {
const f = q.pop();
console.log(f.val);
if(q.leftChild) {
q.unshift(q.leftChild);
}
if(q.rightChild) {
q.unshift(q.rightChild);
}
}
}
近期评论