198 lines
7.3 KiB
JavaScript
198 lines
7.3 KiB
JavaScript
/**
|
|
* LeetCode Hot 100 图解 — 二叉树可视化组件
|
|
* 所有二叉树页面通过 <script src="../shared/tree-viz.js"></script> 引入
|
|
* 依赖: algo-viz.js (StepController, renderCode, renderArray 等)
|
|
*/
|
|
|
|
/* ========== 解析数组表示法 → 树结构 ========== */
|
|
function parseTreeArray(arr) {
|
|
if (!arr || !arr.length) return null;
|
|
const nodes = arr.map((v, i) =>
|
|
(v !== null && v !== undefined) ? {val: v, idx: i, left: null, right: null} : null
|
|
);
|
|
for (let i = 0; i < nodes.length; i++) {
|
|
if (!nodes[i]) continue;
|
|
const li = 2*i+1, ri = 2*i+2;
|
|
if (li < nodes.length) nodes[i].left = nodes[li];
|
|
if (ri < nodes.length) nodes[i].right = nodes[ri];
|
|
}
|
|
return nodes[0];
|
|
}
|
|
|
|
/* ========== 计算树的深度 ========== */
|
|
function treeDepth(root) {
|
|
if (!root) return 0;
|
|
return 1 + Math.max(treeDepth(root.left), treeDepth(root.right));
|
|
}
|
|
|
|
/* ========== SVG 渲染二叉树 ========== */
|
|
function renderTreeSVG(root, options = {}) {
|
|
const {
|
|
highlights = {}, // { nodeIdx: 'current'|'visited'|'active'|'found'|'matched'|'target'|'swap'|'result'|'processing'|'path'|'ancestor'|'ignored'|'left'|'right' }
|
|
depthLabels = {}, // { nodeIdx: number } 显示深度标注
|
|
annotations = {}, // { nodeIdx: string } 节点上方文字
|
|
width = 720,
|
|
nodeR = 20,
|
|
levelH = 72,
|
|
} = options;
|
|
|
|
if (!root) return '<div class="tree-container"><em>空树</em></div>';
|
|
|
|
const depth = treeDepth(root);
|
|
const svgH = depth * levelH + 55;
|
|
|
|
// 递归布局：每个节点居中在其水平范围内
|
|
const pos = {};
|
|
function layout(node, xMin, xMax, y) {
|
|
if (!node) return;
|
|
const x = (xMin + xMax) / 2;
|
|
pos[node.idx] = {x, y, val: node.val};
|
|
layout(node.left, xMin, x, y + levelH);
|
|
layout(node.right, x, xMax, y + levelH);
|
|
}
|
|
layout(root, 40, width - 40, 32 + nodeR);
|
|
|
|
// 颜色方案
|
|
const colorMap = {
|
|
'': {fill:'#dbeafe', stroke:'#3b82f6', text:'#1e40af'},
|
|
'default': {fill:'#dbeafe', stroke:'#3b82f6', text:'#1e40af'},
|
|
'active': {fill:'#c7d2fe', stroke:'#4f46e5', text:'#3730a3', glow:'3b82f6'},
|
|
'current': {fill:'#fef3c7', stroke:'#f59e0b', text:'#92400e', glow:'f59e0b'},
|
|
'visited': {fill:'#dcfce7', stroke:'#16a34a', text:'#166534'},
|
|
'found': {fill:'#fef3c7', stroke:'#f59e0b', text:'#92400e', glow:'f59e0b'},
|
|
'matched': {fill:'#bbf7d0', stroke:'#16a34a', text:'#166534', glow:'16a34a'},
|
|
'target': {fill:'#fce7f3', stroke:'#ec4899', text:'#9d174d', glow:'ec4899'},
|
|
'swap': {fill:'#fef3c7', stroke:'#f59e0b', text:'#92400e', glow:'f59e0b'},
|
|
'left': {fill:'#dbeafe', stroke:'#3b82f6', text:'#1e40af'},
|
|
'right': {fill:'#ede9fe', stroke:'#8b5cf6', text:'#5b21b6'},
|
|
'result': {fill:'#bbf7d0', stroke:'#16a34a', text:'#166534', glow:'16a34a'},
|
|
'processing':{fill:'#e0e7ff', stroke:'#6366f1', text:'#4338ca', glow:'3b82f6'},
|
|
'path': {fill:'#fef9c3', stroke:'#eab308', text:'#854d0e', glow:'f59e0b'},
|
|
'ancestor': {fill:'#fce7f3', stroke:'#ec4899', text:'#9d174d', glow:'ec4899'},
|
|
'ignored': {fill:'#f1f5f9', stroke:'#cbd5e1', text:'#94a3b8'},
|
|
};
|
|
|
|
let svg = `<svg width="${width}" height="${svgH}" viewBox="0 0 ${width} ${svgH}" xmlns="http://www.w3.org/2000/svg" style="max-width:100%;display:block;margin:0 auto;">`;
|
|
|
|
// Defs - 发光滤镜
|
|
svg += '<defs>';
|
|
['3b82f6','f59e0b','16a34a','ec4899'].forEach(id => {
|
|
svg += `<filter id="glow-${id}" x="-50%" y="-50%" width="200%" height="200%">`;
|
|
svg += `<feGaussianBlur stdDeviation="3" result="blur"/>`;
|
|
svg += `<feFlood flood-color="#${id}" flood-opacity="0.3"/>`;
|
|
svg += `<feComposite in2="blur" operator="in"/>`;
|
|
svg += `<feMerge><feMergeNode/><feMergeNode in="SourceGraphic"/></feMerge>`;
|
|
svg += `</filter>`;
|
|
});
|
|
svg += '</defs>';
|
|
|
|
// 边
|
|
function drawEdges(node) {
|
|
if (!node) return;
|
|
const p = pos[node.idx];
|
|
if (!p) return;
|
|
[node.left, node.right].forEach(child => {
|
|
if (child && pos[child.idx]) {
|
|
const c = pos[child.idx];
|
|
const hl = highlights[child.idx] || '';
|
|
let ec = '#cbd5e1';
|
|
if (['current','found','swap','path'].includes(hl)) ec = '#f59e0b';
|
|
else if (['visited','matched','result'].includes(hl)) ec = '#16a34a';
|
|
else if (['active','processing'].includes(hl)) ec = '#6366f1';
|
|
else if (['target','ancestor'].includes(hl)) ec = '#ec4899';
|
|
svg += `<line x1="${p.x}" y1="${p.y+nodeR}" x2="${c.x}" y2="${c.y-nodeR}" stroke="${ec}" stroke-width="2.5" stroke-linecap="round"/>`;
|
|
}
|
|
});
|
|
drawEdges(node.left);
|
|
drawEdges(node.right);
|
|
}
|
|
drawEdges(root);
|
|
|
|
// 节点
|
|
for (const idx in pos) {
|
|
const {x, y, val} = pos[idx];
|
|
const hl = highlights[idx] || '';
|
|
const c = colorMap[hl] || colorMap[''];
|
|
const filterAttr = c.glow ? ` filter="url(#glow-${c.glow})"` : '';
|
|
|
|
svg += `<circle cx="${x}" cy="${y}" r="${nodeR}" fill="${c.fill}" stroke="${c.stroke}" stroke-width="2.5"${filterAttr}/>`;
|
|
svg += `<text x="${x}" y="${y+5}" text-anchor="middle" fill="${c.text}" font-size="14" font-weight="700" font-family="inherit">${val}</text>`;
|
|
|
|
if (annotations[idx]) {
|
|
svg += `<text x="${x}" y="${y-nodeR-8}" text-anchor="middle" fill="#64748b" font-size="11" font-family="inherit">${annotations[idx]}</text>`;
|
|
}
|
|
if (depthLabels[idx] !== undefined) {
|
|
svg += `<text x="${x+nodeR+6}" y="${y+4}" text-anchor="start" fill="#94a3b8" font-size="11" font-style="italic" font-family="inherit">d=${depthLabels[idx]}</text>`;
|
|
}
|
|
}
|
|
|
|
svg += '</svg>';
|
|
return `<div class="tree-container">${svg}</div>`;
|
|
}
|
|
|
|
/* ========== 遍历索引辅助 ========== */
|
|
function inorderIndices(root) {
|
|
const r = [];
|
|
(function dfs(n){ if(!n)return; dfs(n.left); r.push(n.idx); dfs(n.right); })(root);
|
|
return r;
|
|
}
|
|
function preorderIndices(root) {
|
|
const r = [];
|
|
(function dfs(n){ if(!n)return; r.push(n.idx); dfs(n.left); dfs(n.right); })(root);
|
|
return r;
|
|
}
|
|
function postorderIndices(root) {
|
|
const r = [];
|
|
(function dfs(n){ if(!n)return; dfs(n.left); dfs(n.right); r.push(n.idx); })(root);
|
|
return r;
|
|
}
|
|
function levelOrderIndices(root) {
|
|
if (!root) return [];
|
|
const result = [], queue = [root];
|
|
while (queue.length) {
|
|
const level = [], sz = queue.length;
|
|
for (let i = 0; i < sz; i++) {
|
|
const nd = queue.shift();
|
|
level.push(nd.idx);
|
|
if (nd.left) queue.push(nd.left);
|
|
if (nd.right) queue.push(nd.right);
|
|
}
|
|
result.push(level);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
/* ========== 收集所有节点（BFS序） ========== */
|
|
function allNodesBFS(root) {
|
|
if (!root) return [];
|
|
const r = [], queue = [root];
|
|
while (queue.length) {
|
|
const nd = queue.shift();
|
|
r.push(nd);
|
|
if (nd.left) queue.push(nd.left);
|
|
if (nd.right) queue.push(nd.right);
|
|
}
|
|
return r;
|
|
}
|
|
|
|
/* ========== 解析输入字符串 ========== */
|
|
function parseInputTree(str) {
|
|
try {
|
|
const arr = JSON.parse(str.replace(/[()[\]{}]/g, m => m === '[' || m === ']' ? m : ''));
|
|
return arr;
|
|
} catch(e) {
|
|
return null;
|
|
}
|
|
}
|
|
|
|
/* ========== 全局导出 ========== */
|
|
window.parseTreeArray = parseTreeArray;
|
|
window.treeDepth = treeDepth;
|
|
window.renderTreeSVG = renderTreeSVG;
|
|
window.inorderIndices = inorderIndices;
|
|
window.preorderIndices = preorderIndices;
|
|
window.postorderIndices = postorderIndices;
|
|
window.levelOrderIndices = levelOrderIndices;
|
|
window.allNodesBFS = allNodesBFS;
|
|
window.parseInputTree = parseInputTree;
|