树

广度优先遍历

const bfs = (root) => {
	const q = [root]
	while (q.length > 0) {
		const n = q.shift()
		console.log(n.val)
		n.children.forEach((child) => {
			q.push(child)
		})
	}
}

深度优先遍历

const dfs = (root) => {
    console.log(root.val);
    root.children.forEach(dfs);
};

二叉树

先序遍历

递归

const preorder = (root) => {
	if (!root) {
		return
	}
	preorder(root.left)
	console.log(root.val)
	preorder(root.right)
}

非递归

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)
	}
}

中序遍历

递归

const preorder = (root) => {
	if (!root) {
		return
	}
	preorder(root.left)
	console.log(root.val)
	preorder(root.right)
}

非递归

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;
    }
};

后续遍历

递归

const postorder = (root) => {
    if (!root) { return; }
    postorder(root.left);
    postorder(root.right);
    console.log(root.val);
};

非递归

const postorder = (root) => {
    if (!root) { return; }
    const outputStack = [];
    const stack = [root];
    while (stack.length) {
        const n = stack.pop();
        outputStack.push(n);
        if (n.left) stack.push(n.left);
        if (n.right) stack.push(n.right);
    }
    while(outputStack.length){
        const n = outputStack.pop();
        console.log(n.val);
    }
};