如何定义一个二叉树并进行基本的操作,如前序/中序/后序遍历?
参考答案
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)))。
注意递归深度对极深树有栈溢出风险,可用显式栈替代。