- 迭代方法:
queue
:一個陣列,在迭代中,透過push
新增工作,透過shift
進行工作。stack
:一個陣列,在迭代中,透過push
新增工作,透過pop
進行工作。
- 遞迴方法:透過函數的遞迴呼叫來進行
stack
迭代方法。
Breadth First Search,BFS
const bfs = (root) => {
if(!root) return
const queue = [root]
while (queue.length) {
const item = queue.shift()
console.log(item.val)
if(item.left) queue.push(item.left)
if(item.right) queue.push(item.right)
}
}
Depth First Search,DFS
Pre-Order
迭代方法:
const perOrderDfs = (root) => {
if (!root) return
const stack = [root]
while (stack.length) {
const item = stack.pop()
console.log(item.val)
if(item.right) stack.push(item.right)
if(item.left) stack.push(item.left)
}
}
遞迴方法:
const perOrderDfs = (node) => {
if (!node) return
console.log(node.val)
if(node.left) preOrderDfs(node.left)
if(node.right) preOrderDfs(node.right)
}
In-Order
迭代方法:
const inOrderDfs = (root) => {
if (!root) return
const stack = []
let current = root
while (stack.length || current) {
if (current) {
stack.push(current)
current = current.left
} else {
const item = stack.pop()
console.log(item.val)
current = item.right
}
}
}
遞迴方法:
const inOrderDfs = (node) => {
if(!root) return
if(node.left) inOrderDfs(node.left)
console.log(node.val)
if(node.right) inOrderDfs(node.right)
}
Post-Order
迭代方法:
const postOrderDfs = (root) => {
if (!root) return
const stack = [root]
while (stack.length) {
const item = stack.pop()
if (!item) continue
if (!item.val) console.log(item)
stack.push(item.val)
stack.push(item.right)
stack.push(item.left)
}
return result
}
遞迴方法:
const postOrderDfs = (node) => {
if(!root) return
if(node.left) postOrderDfs(node.left)
if(node.right) postOrderDfs(node.right)
console.log(node.val)
}