深度广度遍历
// 根据前序和中序重建二叉树
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
var result = null
if (pre.length === 1) {
result = {
val: pre[0],
left: null,
right: null
}
} else if (pre.length > 1) {
var root = pre[0]
var vinRootIndex = vin.indexOf(root)
var vinLeft = vin.slice(0, vinRootIndex)
var vinRight = vin.slice(vinRootIndex + 1, vin.length)
pre.shift()
var preLeft = pre.slice(0, vinLeft.length)
var preRight = pre.slice(vinLeft.length, pre.length)
result = {
val: root,
left: reConstructBinaryTree(preLeft, vinLeft),
right: reConstructBinaryTree(preRight, vinRight)
}
}
return result
}
// 递归
// 前序遍历
function prevTraverse (node) {
if (node === null) return;
console.log(node.data);
prevTraverse(node.left);
prevTraverse(node.right);
}
// 中序遍历
function middleTraverse (node) {
if (node === null) return;
middleTraverse(node.left);
console.log(node.data);
middleTraverse(node.right);
}
// 后序遍历
function lastTraverse (node) {
if (node === null) return;
lastTraverse(node.left);
lastTraverse(node.right);
console.log(node.data);
}
// 非递归
// 前序遍历
function preTraverse(tree) {
var arr = [],
node = null
arr.unshift(tree)
while (arr.length) {
node = arr.shift()
console.log(node.root)
if (node.right) arr.unshift(node.right)
if (node.left) arr.unshift(node.left)
}
}
// 中序遍历
function middleTraverseUnRecursion (root) {
let arr = [],
node = root;
while (arr.length !== 0 || node !== null) {
if (node === null) {
node = arr.shift();
console.log(node.data);
node = node.right;
} else {
arr.unshift(node);
node = node.left;
}
}
}
// 广度优先-层序遍历
// 递归
var result = []
var stack = [tree]
var count = 0
var bfs = function () {
var node = stack[count]
if (node) {
result.push(node.value)
if (node.left) stack.push(node.left)
if (node.right) stack.push(node.right)
count++
bfs()
}
}
bfs()
console.log(result)
// 非递归
function bfs (node) {
var result = []
var queue = []
queue.push(node)
while (queue.length) {
node = queue.shift()
result.push(node.value)
node.left && queue.push(node.left)
node.right && queue.push(node.right)
}
return result
}
