const binaryTree = {
val: 1,
left: {
val: 2,
left: {val: 4,},
right: {val: 5,}
},
right: {
val: 3,
left: {
val: 6,
left: {val: 8}
},
right: {val: 7,}
}
}
- 先序遍历
const preorder = (root) => {if(!root) return
const stack = [root]
while(stack.length) {const n = stack.pop()
console.log(n.val)
if (n.right) stack.push(n.right)
if (n.left) stack.push(n.left)
}
}
preorder(binaryTree)
- 中序遍历
const inorder = (root) => {if (!root) return
const stack = []
let p = root
while(stack.length || p) {while(p) {stack.push(p)
p = p.left
}
const n = stack.pop()
console.log(n.val)
p = n.right
}
}
inorder(binaryTree)
- 后序遍历
const postorder = (root) => {if (!root) return
const stack = [root]
const res = []
while(stack.length) {const n = stack.pop()
res.push(n)
if (n.left) stack.push(n.left)
if (n.right) stack.push(n.right)
}
while(res.length) {const n = res.pop()
console.log(n.val)
}
}
postorder(binaryTree)