← 返回完整题库
JavaScript困难

如何定义一个二叉树并进行基本的操作,如前序/中序/后序遍历?

参考答案

class Node { constructor(v) { this.val = v; this.left = this.right = null; } }

function preorder(n, out = []) { if (!n) return out; out.push(n.val); preorder(n.left, out); preorder(n.right, out); return out; }
function inorder(n, out = []) { if (!n) return out; inorder(n.left, out); out.push(n.val); inorder(n.right, out); return out; }
function postorder(n, out = []) { if (!n) return out; postorder(n.left, out); postorder(n.right, out); out.push(n.val); return out; }

基本操作

插入(按 BST 规则比较大小递归)、查找、删除(三种情形:叶子/单子/双子用后继替换)、层序遍历(队列)、求高度(1 + max(h(l), h(r)))。

注意递归深度对极深树有栈溢出风险,可用显式栈替代。

本题来自 计算机知识面试题库,共 921 道题。