二叉树
二叉树
前序遍历：ABDECFG 中序遍历：DBEAFCG 后序遍历：DEBFGCA 层序遍历：ABCDEFG
前序遍历（先序遍历） ：
/**
* 前序遍历 -- 递归写法
*/
const preOrder = (root) => {
if (root == null) {
return;
}
console.log(root.val)
preOrder(root.left);
preOrder(root.right);
}
/**
* 前序遍历 -- 利用栈 迭代
*/
const preOrder = (root) => {
}
中序遍历
如果是二叉搜索树，在中序遍历的值就是递增排序
/**
* 中序遍历 -- 递归写法
*/
const inOrder = (root) => {
if (root == null) {
return;
}
inOrder(root.left);
console.log(root.val)
inOrder(root.right);
}
/**
* 中序遍历 -- 利用栈 迭代
*/
const inOrder = (root) => {
const stack = []
const cur = root
while (cur != null || stack.length > 0) {
while(cur != null) {
stack.push(cur)
cur = cur.left
}
cur = cur.pop()
console.log(cur.val)
cur = cur.right
}
}
后序遍历
/**
* 后序遍历 -- 递归写法
*/
const postOrder = (root) => {
if (root == null) {
return
}
postOrder(root.left)
postOrder(root.right)
console.log(root.val)
}
/**
* 后序遍历 -- 利用栈 迭代
*/
const postOrder = (root) => {
}
层序遍历
/**
* 层序遍历 -- 利用队列辅助
*/
const levelOrder = (root) => {
const queue = []
queue.push(root)
while (queue.length > 0) {
const cur = queue.shift()
console.log(cur.val)
if (cur.left) {
queue.push(cur.left)
}
if (cur.right) {
queue.push(cur.right)
}
}
}