1455 lines
64 KiB
Python
1455 lines
64 KiB
Python
"""Binary-tree algorithm JS generators for LeetCode Hot 100 图解."""
|
||
|
||
# Common JS helpers – inline in each function so pages are self-contained
|
||
_TREE_UTILS = r'''
|
||
function arrayToTree(arr) {
|
||
if (!arr || arr.length === 0) return null;
|
||
let idCtr = 0;
|
||
const nodes = arr.map(v => v === null ? null : {val: v, left: null, right: null, _id: 'n' + (idCtr++)});
|
||
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 treeToArray(root) {
|
||
if (!root) return [];
|
||
const res = [], q = [root];
|
||
while (q.length) {
|
||
const n = q.shift();
|
||
if (n === null) { res.push(null); continue; }
|
||
res.push(n.val); q.push(n.left, n.right);
|
||
}
|
||
while (res.length && res[res.length-1] === null) res.pop();
|
||
return res;
|
||
}
|
||
function deepClone(node) {
|
||
if (!node) return null;
|
||
return {val: node.val, _id: node._id, left: deepClone(node.left), right: deepClone(node.right)};
|
||
}
|
||
'''
|
||
|
||
def js_binary_tree_inorder_traversal():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [1,null,2,3], label: '示例1: [1,null,2,3] → [1,3,2]'},
|
||
{tree: [2,1,3], label: '示例2: [2,1,3] → [1,2,3]'},
|
||
{tree: [1,2,3,4,5,6,7], label: '示例3: [1,2,3,4,5,6,7]'},
|
||
];
|
||
let root, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
root = arrayToTree(arr);
|
||
steps = []; const result = [];
|
||
const stack = []; let cur = root;
|
||
steps.push({stage:'init',hl:{},stack:[],result:[],msg:'初始化：空栈，当前指针指向根节点，中序遍历 左→根→右'});
|
||
|
||
while (cur || stack.length) {
|
||
while (cur) {
|
||
stack.push(cur);
|
||
steps.push({stage:'push',hl:{[cur._id]:'active'},stack:stack.map(n=>n.val),result:[...result],
|
||
msg:`走到节点 ${cur.val}，入栈`});
|
||
cur = cur.left;
|
||
}
|
||
cur = stack.pop();
|
||
result.push(cur.val);
|
||
steps.push({stage:'visit',hl:{[cur._id]:'current'},stack:stack.map(n=>n.val),result:[...result],
|
||
msg:`弹出栈顶 ${cur.val}，访问（加入结果）：[${result.join(',')}]`});
|
||
cur = cur.right;
|
||
}
|
||
steps.push({stage:'done',hl:{},stack:[],result:[...result],msg:`中序遍历完成：[${result.join(',')}]`});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderBinaryTree(root, {highlights: s.hl});
|
||
viz += '<div style="margin-top:12px;"><b>栈：</b></div>';
|
||
viz += renderStack(s.stack, {topIndex: s.stack.length-1});
|
||
if (s.result.length) viz += '<div style="margin-top:8px;"><b>结果：</b>[' + s.result.join(', ') + ']</div>';
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">中序遍历结果 = <b>[${s.result}]</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','push→入栈','visit→访问','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[1,null,2,3]';
|
||
buildSteps(examples[0].tree);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法数组，如 [1,null,2,3]'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree);
|
||
buildSteps(e.tree); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def inorderTraversal(root):
|
||
res, stack = [], []
|
||
cur = root
|
||
while cur or stack:
|
||
while cur:
|
||
stack.append(cur)
|
||
cur = cur.left
|
||
cur = stack.pop()
|
||
res.append(cur.val)
|
||
cur = cur.right
|
||
return res`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_maximum_depth_of_binary_tree():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [3,9,20,null,null,15,7], label: '示例1: [3,9,20,null,null,15,7] → 3'},
|
||
{tree: [1,null,2], label: '示例2: [1,null,2] → 2'},
|
||
{tree: [], label: '示例3: [] → 0'},
|
||
];
|
||
let root, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
root = arrayToTree(arr);
|
||
steps = [];
|
||
if (!root) { steps.push({stage:'done',hl:{},msg:'空树，深度 = 0',depth:0}); return; }
|
||
|
||
function dfs(node) {
|
||
if (!node) return 0;
|
||
steps.push({stage:'enter', hl:{[node._id]:'current'}, msg:`进入节点 ${node.val}`});
|
||
if (!node.left && !node.right) {
|
||
steps.push({stage:'leaf', hl:{[node._id]:'visited'}, msg:`节点 ${node.val} 是叶子，返回深度 1`, depth:1});
|
||
return 1;
|
||
}
|
||
const ld = node.left ? dfs(node.left) : 0;
|
||
const rd = node.right ? dfs(node.right) : 0;
|
||
const depth = Math.max(ld, rd) + 1;
|
||
steps.push({stage:'return', hl:{[node._id]:'visited'}, msg:`节点 ${node.val}：左深度=${ld}，右深度=${rd}，max(${ld},${rd})+1 = ${depth}`, depth});
|
||
return depth;
|
||
}
|
||
dfs(root);
|
||
const finalDepth = steps[steps.length-1].depth;
|
||
steps.push({stage:'done', hl:{}, msg:`最大深度 = ${finalDepth}`, depth:finalDepth});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderBinaryTree(root, {highlights: s.hl});
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.depth !== undefined) {
|
||
$('detailContent').innerHTML += `<div class="current-answer">当前计算深度：<b>${s.depth}</b></div>`;
|
||
}
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">最大深度 = <b>${s.depth}</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['enter→进入','leaf→叶子','return→返回','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[3,9,20,null,null,15,7]';
|
||
buildSteps(examples[0].tree);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree);
|
||
buildSteps(e.tree); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def maxDepth(root):
|
||
if not root:
|
||
return 0
|
||
left = maxDepth(root.left)
|
||
right = maxDepth(root.right)
|
||
return max(left, right) + 1`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_invert_binary_tree():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [4,2,7,1,3,6,9], label: '示例1: [4,2,7,1,3,6,9]'},
|
||
{tree: [2,1,3], label: '示例2: [2,1,3]'},
|
||
{tree: [], label: '示例3: []'},
|
||
];
|
||
let root, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
root = arrayToTree(arr);
|
||
steps = [];
|
||
if (!root) { steps.push({stage:'done',hl:{},snap:null,msg:'空树无需翻转'}); return; }
|
||
|
||
function saveTree(node) {
|
||
if (!node) return null;
|
||
return {val:node.val, _id:node._id, left:saveTree(node.left), right:saveTree(node.right)};
|
||
}
|
||
|
||
function dfs(node) {
|
||
if (!node) return;
|
||
steps.push({stage:'visit', hl:{[node._id]:'current'}, msg:`访问节点 ${node.val}，准备交换左右子树`, snap:saveTree(root)});
|
||
const tmp = node.left;
|
||
node.left = node.right;
|
||
node.right = tmp;
|
||
steps.push({stage:'swap', hl:{[node._id]:'active'}, msg:`交换节点 ${node.val} 的左右子树完成`, snap:saveTree(root)});
|
||
dfs(node.left);
|
||
dfs(node.right);
|
||
}
|
||
dfs(root);
|
||
steps.push({stage:'done', hl:{}, msg:'翻转完成！', snap:saveTree(root)});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderBinaryTree(s.snap || root, {highlights: s.hl});
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">翻转后的树 = <b>[${treeToArray(s.snap || root)}]</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['visit→访问','swap→交换','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[4,2,7,1,3,6,9]';
|
||
buildSteps(examples[0].tree);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree);
|
||
buildSteps(e.tree); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def invertTree(root):
|
||
if not root:
|
||
return None
|
||
root.left, root.right = root.right, root.left
|
||
invertTree(root.left)
|
||
invertTree(root.right)
|
||
return root`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_symmetric_tree():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [1,2,2,3,4,4,3], label: '示例1: 对称 [1,2,2,3,4,4,3]'},
|
||
{tree: [1,2,2,null,3,null,3], label: '示例2: 不对称 [1,2,2,null,3,null,3]'},
|
||
{tree: [1], label: '示例3: [1] 单节点'},
|
||
];
|
||
let root, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
root = arrayToTree(arr);
|
||
steps = [];
|
||
if (!root) { steps.push({stage:'done',hl:{},msg:'空树是对称的',isSym:true}); return; }
|
||
steps.push({stage:'init',hl:{},msg:'递归检查左右子树是否镜像对称',isSym:true});
|
||
|
||
function check(a, b) {
|
||
if (!a && !b) {
|
||
steps.push({stage:'match',hl:{},msg:'两个节点都为空，匹配 ✓',isSym:true});
|
||
return true;
|
||
}
|
||
if (!a || !b) {
|
||
const nonNull = a || b;
|
||
steps.push({stage:'mismatch',hl:{[nonNull._id]:'current'},msg:'一侧为空另一侧不为空，不匹配 ✗',isSym:false});
|
||
return false;
|
||
}
|
||
if (a.val !== b.val) {
|
||
steps.push({stage:'mismatch',hl:{[a._id]:'current',[b._id]:'current'},msg:`节点 ${a.val} ≠ ${b.val}，不匹配 ✗`,isSym:false});
|
||
return false;
|
||
}
|
||
steps.push({stage:'compare',hl:{[a._id]:'active',[b._id]:'active'},msg:`比较 ${a.val} 和 ${b.val}，相等 ✓`,isSym:true});
|
||
const outer = check(a.left, b.right);
|
||
if (!outer) return false;
|
||
return check(a.right, b.left);
|
||
}
|
||
const isSym = check(root.left, root.right);
|
||
steps.push({stage:'done',hl:{},msg:`判断结果：${isSym?'对称 ✓':'不对称 ✗'}`,isSym});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderBinaryTree(root, {highlights: s.hl});
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer"${!s.isSym?' style="border-color:#f87171;background:#fef2f2;"':''}>是否对称：<b>${s.isSym?'是 ✓':'否 ✗'}</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','compare→比较','match→匹配','mismatch→不匹配','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[1,2,2,3,4,4,3]';
|
||
buildSteps(examples[0].tree);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree);
|
||
buildSteps(e.tree); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def isSymmetric(root):
|
||
def check(a, b):
|
||
if not a and not b: return True
|
||
if not a or not b: return False
|
||
return a.val == b.val and check(a.left, b.right) and check(a.right, b.left)
|
||
return check(root.left, root.right) if root else True`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_diameter_of_binary_tree():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [1,2,3,4,5], label: '示例1: [1,2,3,4,5] 直径=3'},
|
||
{tree: [1,2], label: '示例2: [1,2] 直径=1'},
|
||
{tree: [1,2,3,4], label: '示例3: [1,2,3,4]'},
|
||
];
|
||
let root, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
root = arrayToTree(arr);
|
||
steps = [];
|
||
let maxDiameter = 0;
|
||
steps.push({stage:'init',hl:{},msg:'DFS 返回每个节点的深度，维护最大直径（左深度+右深度）',maxDia:0});
|
||
|
||
function dfs(node) {
|
||
if (!node) return 0;
|
||
steps.push({stage:'enter',hl:{[node._id]:'current'},msg:`进入节点 ${node.val}`,maxDia:maxDiameter});
|
||
const ld = dfs(node.left);
|
||
const rd = dfs(node.right);
|
||
const diameter = ld + rd;
|
||
if (diameter > maxDiameter) maxDiameter = diameter;
|
||
const depth = Math.max(ld, rd) + 1;
|
||
steps.push({stage:'calc',hl:{[node._id]:'visited'},msg:`节点 ${node.val}：左深=${ld}，右深=${rd}，直径=${ld}+${rd}=${diameter}，最大直径=${maxDiameter}，返回深度=${depth}`,maxDia:maxDiameter,depth});
|
||
return depth;
|
||
}
|
||
if (root) dfs(root);
|
||
steps.push({stage:'done',hl:{},msg:`最大直径 = ${maxDiameter}`,maxDia:maxDiameter});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderBinaryTree(root, {highlights: s.hl});
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.maxDia !== undefined) {
|
||
$('detailContent').innerHTML += `<div class="current-answer">当前最大直径：<b>${s.maxDia}</b></div>`;
|
||
}
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">二叉树的直径 = <b>${s.maxDia}</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','enter→进入','calc→计算','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[1,2,3,4,5]';
|
||
buildSteps(examples[0].tree);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree);
|
||
buildSteps(e.tree); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def diameterOfBinaryTree(root):
|
||
max_d = 0
|
||
def depth(node):
|
||
nonlocal max_d
|
||
if not node: return 0
|
||
l = depth(node.left)
|
||
r = depth(node.right)
|
||
max_d = max(max_d, l + r)
|
||
return max(l, r) + 1
|
||
depth(root)
|
||
return max_d`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_binary_tree_level_order_traversal():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [3,9,20,null,null,15,7], label: '示例1: [3,9,20,null,null,15,7]'},
|
||
{tree: [1], label: '示例2: [1]'},
|
||
{tree: [], label: '示例3: []'},
|
||
];
|
||
let root, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
root = arrayToTree(arr);
|
||
steps = [];
|
||
if (!root) { steps.push({stage:'done',hl:{},queue:[],result:[],msg:'空树，返回 []'}); return; }
|
||
|
||
const queue = [root]; const result = []; let level = 0;
|
||
steps.push({stage:'init',hl:{},queue:[root.val],result:[],msg:'初始化队列，根节点入队'});
|
||
|
||
while (queue.length) {
|
||
const size = queue.length;
|
||
const levelVals = [];
|
||
const levelNodes = [];
|
||
steps.push({stage:'start_level',hl:{},queue:queue.map(n=>n.val),result:JSON.parse(JSON.stringify(result)),msg:`开始处理第 ${level} 层，本层 ${size} 个节点`});
|
||
|
||
for (let i = 0; i < size; i++) {
|
||
const node = queue.shift();
|
||
levelVals.push(node.val);
|
||
levelNodes.push(node);
|
||
const hl = {[node._id]:'current'};
|
||
levelNodes.forEach((n,j) => { if (j < levelVals.length-1) hl[n._id] = 'visited'; });
|
||
if (node.left) queue.push(node.left);
|
||
if (node.right) queue.push(node.right);
|
||
steps.push({stage:'visit',hl,queue:queue.map(n=>n.val),result:JSON.parse(JSON.stringify(result)),msg:`访问节点 ${node.val}`});
|
||
}
|
||
result.push(levelVals);
|
||
const hl2 = {}; levelNodes.forEach(n => hl2[n._id] = 'visited');
|
||
steps.push({stage:'end_level',hl:hl2,queue:queue.map(n=>n.val),result:JSON.parse(JSON.stringify(result)),msg:`第 ${level} 层完成：[${levelVals}]`});
|
||
level++;
|
||
}
|
||
steps.push({stage:'done',hl:{},queue:[],result:JSON.parse(JSON.stringify(result)),msg:'层序遍历完成'});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderBinaryTree(root, {highlights: s.hl});
|
||
viz += '<div style="margin-top:12px;"><b>队列：</b></div>';
|
||
viz += renderQueue(s.queue);
|
||
viz += '<div style="margin-top:8px;"><b>结果：</b>' + JSON.stringify(s.result) + '</div>';
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">层序遍历 = <b>${JSON.stringify(s.result)}</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','start_level→开始层','visit→访问','end_level→完成层','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[3,9,20,null,null,15,7]';
|
||
buildSteps(examples[0].tree);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree);
|
||
buildSteps(e.tree); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def levelOrder(root):
|
||
if not root: return []
|
||
res, queue = [], [root]
|
||
while queue:
|
||
level = []
|
||
for _ in range(len(queue)):
|
||
node = queue.pop(0)
|
||
level.append(node.val)
|
||
if node.left: queue.append(node.left)
|
||
if node.right: queue.append(node.right)
|
||
res.append(level)
|
||
return res`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_convert_sorted_array_to_bst():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{input: [-10,-3,0,5,9], label: '示例1: [-10,-3,0,5,9]'},
|
||
{input: [1,3], label: '示例2: [1,3]'},
|
||
{input: [1,2,3,4], label: '示例3: [1,2,3,4]'},
|
||
];
|
||
let nums, steps, stepCtrl, builtRoot;
|
||
let idCtr;
|
||
|
||
function buildSteps(arr) {
|
||
nums = [...arr]; steps = []; idCtr = 0;
|
||
steps.push({stage:'init', hl:{}, lo:0, hi:arr.length-1, mid:-1, msg:'二分递归构造平衡 BST：取中间元素为根'});
|
||
|
||
function build(lo, hi) {
|
||
if (lo > hi) return null;
|
||
const mid = Math.floor((lo + hi) / 2);
|
||
const node = {val: arr[mid], _id: 'n' + (idCtr++), left: null, right: null};
|
||
const hl = {};
|
||
for (let i = lo; i <= hi; i++) hl[i] = i === mid ? 'orange' : 'blue';
|
||
steps.push({stage:'select', hl, mid, lo, hi, msg:`范围 [${lo},${hi}]，mid=${mid}，nums[${mid}]=${arr[mid]} 作为根`});
|
||
node.left = build(lo, mid - 1);
|
||
node.right = build(mid + 1, hi);
|
||
return node;
|
||
}
|
||
builtRoot = build(0, arr.length - 1);
|
||
steps.push({stage:'done', hl:{}, lo:0, hi:arr.length-1, mid:-1, msg:'构造完成！'});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = '<div style="margin-bottom:8px;"><b>有序数组：</b></div>';
|
||
viz += renderArray(nums, {highlights: s.hl || {}});
|
||
if (s.lo !== undefined) {
|
||
viz += `<div style="margin-top:4px;font-size:13px;color:var(--text-secondary);">范围: [${s.lo}, ${s.hi}]${s.mid>=0 ? ' mid='+s.mid+' 值='+nums[s.mid] : ''}</div>`;
|
||
}
|
||
if (builtRoot) {
|
||
viz += '<div style="margin-top:12px;"><b>构造中的 BST：</b></div>';
|
||
viz += renderBinaryTree(builtRoot, {highlights: {}});
|
||
}
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">BST 构建完成 = <b>[${treeToArray(builtRoot)}]</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','select→选中间','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[-10,-3,0,5,9]';
|
||
buildSteps(examples[0].input);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法升序数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.input);
|
||
buildSteps(e.input); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def sortedArrayToBST(nums):
|
||
def build(lo, hi):
|
||
if lo > hi: return None
|
||
mid = (lo + hi) // 2
|
||
root = TreeNode(nums[mid])
|
||
root.left = build(lo, mid - 1)
|
||
root.right = build(mid + 1, hi)
|
||
return root
|
||
return build(0, len(nums) - 1)`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_validate_binary_search_tree():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [2,1,3], label: '示例1: [2,1,3] 有效 BST'},
|
||
{tree: [5,1,4,null,null,3,6], label: '示例2: [5,1,4,null,null,3,6] 无效'},
|
||
{tree: [5,4,6,null,null,3,7], label: '示例3: [5,4,6,null,null,3,7] 无效'},
|
||
];
|
||
let root, steps, stepCtrl, inorderArr;
|
||
|
||
function buildSteps(arr) {
|
||
root = arrayToTree(arr);
|
||
steps = []; inorderArr = [];
|
||
if (!root) { steps.push({stage:'done',hl:{},msg:'空树是有效 BST',valid:true}); return; }
|
||
|
||
const stack = []; let cur = root; let prev = null; let valid = true;
|
||
steps.push({stage:'init',hl:{},msg:'中序遍历 BST，检查结果是否严格递增',valid:true});
|
||
|
||
while (cur || stack.length) {
|
||
while (cur) {
|
||
stack.push(cur);
|
||
steps.push({stage:'push',hl:{[cur._id]:'active'},msg:`走到节点 ${cur.val}，入栈`,valid});
|
||
cur = cur.left;
|
||
}
|
||
cur = stack.pop();
|
||
inorderArr.push(cur.val);
|
||
if (prev !== null && cur.val <= prev) {
|
||
valid = false;
|
||
steps.push({stage:'invalid',hl:{[cur._id]:'current'},msg:`${cur.val} ≤ 上一个值 ${prev}，不是严格递增！无效 BST ✗`,valid:false,inorder:[...inorderArr]});
|
||
} else {
|
||
steps.push({stage:'visit',hl:{[cur._id]:'visited'},msg:`访问 ${cur.val}，大于上一个值 ${prev !== null ? prev : '-∞'} ✓`,valid,inorder:[...inorderArr]});
|
||
}
|
||
prev = cur.val;
|
||
cur = cur.right;
|
||
}
|
||
steps.push({stage:'done',hl:{},msg:valid ? '中序遍历严格递增，有效 BST ✓' : '中序遍历不严格递增，无效 BST ✗',valid,inorder:[...inorderArr]});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderBinaryTree(root, {highlights: s.hl});
|
||
if (s.inorder && s.inorder.length) {
|
||
viz += '<div style="margin-top:10px;"><b>中序序列：</b>[' + s.inorder.join(', ') + ']</div>';
|
||
}
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer"${!s.valid?' style="border-color:#f87171;background:#fef2f2;"':''}>是否有效 BST：<b>${s.valid?'是 ✓':'否 ✗'}</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','push→入栈','visit→访问','invalid→无效','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[2,1,3]';
|
||
buildSteps(examples[0].tree);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree);
|
||
buildSteps(e.tree); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def isValidBST(root):
|
||
stack, prev = [], None
|
||
cur = root
|
||
while cur or stack:
|
||
while cur:
|
||
stack.append(cur)
|
||
cur = cur.left
|
||
cur = stack.pop()
|
||
if prev is not None and cur.val <= prev:
|
||
return False
|
||
prev = cur.val
|
||
cur = cur.right
|
||
return True`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_kth_smallest_element_in_a_bst():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [3,1,4,null,2], k: 1, label: '示例1: [3,1,4,null,2], k=1'},
|
||
{tree: [5,3,6,2,4,null,null,1], k: 3, label: '示例2: [5,3,6,2,4,null,null,1], k=3'},
|
||
];
|
||
let root, steps, stepCtrl;
|
||
|
||
function buildSteps(arr, k) {
|
||
root = arrayToTree(arr);
|
||
steps = [];
|
||
const stack = []; let cur = root; let count = 0;
|
||
steps.push({stage:'init',hl:{},msg:`寻找第 ${k} 小的元素，中序遍历 BST`,count:0,k,result:null});
|
||
|
||
while (cur || stack.length) {
|
||
while (cur) {
|
||
stack.push(cur);
|
||
steps.push({stage:'push',hl:{[cur._id]:'active'},msg:`走到节点 ${cur.val}，入栈`,count,k,result:null});
|
||
cur = cur.left;
|
||
}
|
||
cur = stack.pop();
|
||
count++;
|
||
const found = count === k;
|
||
steps.push({stage:'visit',hl:{[cur._id]:found?'current':'visited'},msg:`访问 ${cur.val}，第 ${count} 小${found?' — 找到！':''}`,count,k,result:found?cur.val:null});
|
||
if (found) {
|
||
steps.push({stage:'done',hl:{[cur._id]:'current'},msg:`第 ${k} 小的元素是 ${cur.val}`,count,k,result:cur.val});
|
||
return;
|
||
}
|
||
cur = cur.right;
|
||
}
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderBinaryTree(root, {highlights: s.hl});
|
||
viz += `<div style="margin-top:10px;">已访问 <b>${s.count}</b> / ${s.k} 个节点</div>`;
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">第 ${s.k} 小的元素 = <b>${s.result}</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','push→入栈','visit→访问','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[3,1,4,null,2], k=1';
|
||
buildSteps(examples[0].tree, examples[0].k);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
const m = $('inputArea').value.match(/\[([^\]]+)\].*k\s*=\s*(\d+)/);
|
||
if (!m) { alert('格式: [3,1,4,null,2], k=1'); return; }
|
||
const arr = JSON.parse('['+m[1]+']'); const k = parseInt(m[2]);
|
||
buildSteps(arr, k); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree) + ', k=' + e.k;
|
||
buildSteps(e.tree, e.k); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def kthSmallest(root, k):
|
||
stack, count = [], 0
|
||
cur = root
|
||
while cur or stack:
|
||
while cur:
|
||
stack.append(cur)
|
||
cur = cur.left
|
||
cur = stack.pop()
|
||
count += 1
|
||
if count == k:
|
||
return cur.val
|
||
cur = cur.right`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_binary_tree_right_side_view():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [1,2,3,null,5,null,4], label: '示例1: [1,2,3,null,5,null,4]'},
|
||
{tree: [1,null,3], label: '示例2: [1,null,3]'},
|
||
{tree: [1,2,3,4], label: '示例3: [1,2,3,4]'},
|
||
];
|
||
let root, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
root = arrayToTree(arr);
|
||
steps = [];
|
||
if (!root) { steps.push({stage:'done',hl:{},result:[],msg:'空树，右视图为 []'}); return; }
|
||
|
||
const queue = [root]; const result = []; let level = 0;
|
||
steps.push({stage:'init',hl:{},queue:[root.val],result:[],msg:'BFS 逐层遍历，取每层最后一个节点'});
|
||
|
||
while (queue.length) {
|
||
const size = queue.length;
|
||
let rightNode = null;
|
||
const levelNodes = [];
|
||
for (let i = 0; i < size; i++) {
|
||
const node = queue.shift();
|
||
levelNodes.push(node);
|
||
if (node.left) queue.push(node.left);
|
||
if (node.right) queue.push(node.right);
|
||
if (i === size - 1) rightNode = node;
|
||
}
|
||
const hl = {};
|
||
levelNodes.forEach((n,i) => hl[n._id] = i === size-1 ? 'current' : 'visited');
|
||
result.push(rightNode.val);
|
||
steps.push({stage:'level',hl,queue:queue.map(n=>n.val),result:[...result],msg:`第 ${level} 层：[${levelNodes.map(n=>n.val)}]，最右 = ${rightNode.val}`});
|
||
level++;
|
||
}
|
||
steps.push({stage:'done',hl:{},queue:[],result:[...result],msg:'右视图 = [' + result.join(', ') + ']'});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderBinaryTree(root, {highlights: s.hl});
|
||
viz += '<div style="margin-top:12px;"><b>队列：</b></div>';
|
||
viz += renderQueue(s.queue);
|
||
viz += '<div style="margin-top:8px;"><b>右视图：</b>[' + s.result.join(', ') + ']</div>';
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">右视图 = <b>[${s.result}]</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','level→逐层','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[1,2,3,null,5,null,4]';
|
||
buildSteps(examples[0].tree);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree);
|
||
buildSteps(e.tree); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def rightSideView(root):
|
||
if not root: return []
|
||
res, queue = [], [root]
|
||
while queue:
|
||
size = len(queue)
|
||
for i in range(size):
|
||
node = queue.pop(0)
|
||
if i == size - 1:
|
||
res.append(node.val)
|
||
if node.left: queue.append(node.left)
|
||
if node.right: queue.append(node.right)
|
||
return res`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_flatten_binary_tree_to_linked_list():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [1,2,5,3,4,null,6], label: '示例1: [1,2,5,3,4,null,6]'},
|
||
{tree: [], label: '示例2: []'},
|
||
{tree: [1,2], label: '示例3: [1,2]'},
|
||
];
|
||
let root, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
root = arrayToTree(arr);
|
||
steps = [];
|
||
if (!root) { steps.push({stage:'done',hl:{},snap:null,msg:'空树无需展开'}); return; }
|
||
|
||
function saveTree(node) {
|
||
if (!node) return null;
|
||
return {val:node.val, _id:node._id, left:saveTree(node.left), right:saveTree(node.right)};
|
||
}
|
||
|
||
steps.push({stage:'init',hl:{},snap:saveTree(root),msg:'前序遍历，原地修改为右偏链表'});
|
||
|
||
let cur = root;
|
||
while (cur) {
|
||
if (cur.left) {
|
||
let pred = cur.left;
|
||
const path = [pred.val];
|
||
while (pred.right) { pred = pred.right; path.push(pred.val); }
|
||
steps.push({stage:'find',hl:{[cur._id]:'current',[pred._id]:'active'},snap:saveTree(root),msg:`节点 ${cur.val} 有左子树，找前驱（左子树最右）= ${pred.val}，路径：${path.join('→')}`});
|
||
pred.right = cur.right;
|
||
cur.right = cur.left;
|
||
cur.left = null;
|
||
steps.push({stage:'reconnect',hl:{[cur._id]:'current'},snap:saveTree(root),msg:`前驱右指针→${cur.val}原右子树，${cur.val}.right→左子树，left=null`});
|
||
} else {
|
||
steps.push({stage:'skip',hl:{[cur._id]:'visited'},snap:saveTree(root),msg:`节点 ${cur.val} 无左子树，向右移动`});
|
||
}
|
||
cur = cur.right;
|
||
}
|
||
steps.push({stage:'done',hl:{},snap:saveTree(root),msg:'展开完成！'});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = '<div style="margin-bottom:8px;"><b>当前树结构：</b></div>';
|
||
viz += renderBinaryTree(s.snap, {highlights: s.hl});
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') {
|
||
const arr = treeToArray(s.snap);
|
||
$('resultContent').innerHTML = `<div class="final-answer">展开后 = <b>[${arr}]</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','find→找前驱','reconnect→重连','skip→跳过','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[1,2,5,3,4,null,6]';
|
||
buildSteps(examples[0].tree);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree);
|
||
buildSteps(e.tree); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def flatten(root):
|
||
cur = root
|
||
while cur:
|
||
if cur.left:
|
||
pred = cur.left
|
||
while pred.right:
|
||
pred = pred.right
|
||
pred.right = cur.right
|
||
cur.right = cur.left
|
||
cur.left = None
|
||
cur = cur.right`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_construct_binary_tree_from_preorder_and_inorder():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{preorder: [3,9,20,15,7], inorder: [9,3,15,20,7], label: '示例1: pre=[3,9,20,15,7] in=[9,3,15,20,7]'},
|
||
{preorder: [-1], inorder: [-1], label: '示例2: 单节点'},
|
||
];
|
||
let preo, ino, steps, stepCtrl, builtRoot;
|
||
let idCtr;
|
||
|
||
function buildSteps(pre, ine) {
|
||
preo = [...pre]; ino = [...ine];
|
||
steps = []; idCtr = 0;
|
||
const inMap = {};
|
||
ine.forEach((v,i) => inMap[v] = i);
|
||
|
||
steps.push({stage:'init', hlPre:{}, hlIn:{}, msg:'前序找根，中序分左右，递归构造'});
|
||
|
||
function build(pl, pr, il, ir) {
|
||
if (pl > pr) return null;
|
||
const rootVal = pre[pl];
|
||
const node = {val: rootVal, _id: 'n' + (idCtr++), left: null, right: null};
|
||
const inIdx = inMap[rootVal];
|
||
const leftSize = inIdx - il;
|
||
const hlPre = {}, hlIn = {};
|
||
hlPre[pl] = 'orange';
|
||
for (let i = pl+1; i <= pr; i++) hlPre[i] = 'default';
|
||
for (let i = il; i <= ir; i++) hlIn[i] = i === inIdx ? 'orange' : (i < inIdx ? 'blue' : 'purple');
|
||
|
||
steps.push({stage:'select', hlPre, hlIn, msg:`根 = pre[${pl}]=${rootVal}，中序位置=${inIdx}，左子树 ${leftSize} 个，右子树 ${pr-pl-leftSize} 个`, rootVal, inIdx});
|
||
node.left = build(pl + 1, pl + leftSize, il, inIdx - 1);
|
||
node.right = build(pl + leftSize + 1, pr, inIdx + 1, ir);
|
||
return node;
|
||
}
|
||
builtRoot = build(0, pre.length - 1, 0, ine.length - 1);
|
||
steps.push({stage:'done', hlPre:{}, hlIn:{}, msg:'构造完成！'});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = '<div><b>前序：</b></div>';
|
||
viz += renderArray(preo, {highlights: s.hlPre || {}});
|
||
viz += '<div style="margin-top:6px;"><b>中序：</b></div>';
|
||
viz += renderArray(ino, {highlights: s.hlIn || {}});
|
||
if (s.inIdx !== undefined) {
|
||
viz += `<div class="partition-legend" style="margin-top:6px;">
|
||
<span><span class="dot-lg" style="background:var(--blue-light);"></span> 左子树</span>
|
||
<span><span class="dot-lg" style="background:var(--orange-light);"></span> 根</span>
|
||
<span><span class="dot-lg" style="background:var(--purple-light);"></span> 右子树</span>
|
||
</div>`;
|
||
}
|
||
if (builtRoot) {
|
||
viz += '<div style="margin-top:10px;"><b>构造中的树：</b></div>';
|
||
viz += renderBinaryTree(builtRoot, {highlights: {}});
|
||
}
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">构造的树 = <b>[${treeToArray(builtRoot)}]</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','select→选根','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = 'pre=[3,9,20,15,7] in=[9,3,15,20,7]';
|
||
buildSteps(examples[0].preorder, examples[0].inorder);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
const m = $('inputArea').value.match(/pre=\[([^\]]+)\].*in=\[([^\]]+)\]/);
|
||
if (!m) { alert('格式: pre=[3,9,20,15,7] in=[9,3,15,20,7]'); return; }
|
||
const pre = JSON.parse('['+m[1]+']'), ine = JSON.parse('['+m[2]+']');
|
||
buildSteps(pre, ine); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = `pre=[${e.preorder}] in=[${e.inorder}]`;
|
||
buildSteps(e.preorder, e.inorder); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def buildTree(preorder, inorder):
|
||
in_map = {v: i for i, v in enumerate(inorder)}
|
||
def build(pl, pr, il, ir):
|
||
if pl > pr: return None
|
||
root_val = preorder[pl]
|
||
idx = in_map[root_val]
|
||
left_size = idx - il
|
||
root = TreeNode(root_val)
|
||
root.left = build(pl+1, pl+left_size, il, idx-1)
|
||
root.right = build(pl+left_size+1, pr, idx+1, ir)
|
||
return root
|
||
return build(0, len(preorder)-1, 0, len(inorder)-1)`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_path_sum_iii():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [10,5,-3,3,2,null,11,3,-2,null,1], target: 8, label: '示例1: target=8 → 3'},
|
||
{tree: [5,4,8,11,null,13,4,7,2,null,null,5,1], target: 22, label: '示例2: target=22 → 3'},
|
||
];
|
||
let root, steps, stepCtrl;
|
||
|
||
function buildSteps(arr, target) {
|
||
root = arrayToTree(arr);
|
||
steps = [];
|
||
let count = 0;
|
||
const prefixSum = {0: 1};
|
||
|
||
steps.push({stage:'init', hl:{}, msg:`前缀和 DFS，targetSum=${target}，初始 {0:1}`, prefixSum:{0:1}, currentSum:0, count:0, path:[]});
|
||
|
||
function dfs(node, currSum, path) {
|
||
if (!node) return;
|
||
currSum += node.val;
|
||
path.push(node.val);
|
||
const need = currSum - target;
|
||
const found = prefixSum[need] || 0;
|
||
|
||
if (found > 0) {
|
||
count += found;
|
||
steps.push({stage:'found', hl:{[node._id]:'current'}, msg:`节点 ${node.val}：前缀和=${currSum}，需 ${currSum}-${target}=${need}，出现 ${found} 次，+${found}=${count}`, prefixSum:JSON.parse(JSON.stringify(prefixSum)), currentSum:currSum, count, path:[...path]});
|
||
} else {
|
||
steps.push({stage:'visit', hl:{[node._id]:'active'}, msg:`节点 ${node.val}：前缀和=${currSum}，需 ${need}，未出现`, prefixSum:JSON.parse(JSON.stringify(prefixSum)), currentSum:currSum, count, path:[...path]});
|
||
}
|
||
|
||
prefixSum[currSum] = (prefixSum[currSum] || 0) + 1;
|
||
steps.push({stage:'add_prefix', hl:{[node._id]:'visited'}, msg:`前缀和 ${currSum} 计数+1`, prefixSum:JSON.parse(JSON.stringify(prefixSum)), currentSum:currSum, count, path:[...path]});
|
||
|
||
dfs(node.left, currSum, path);
|
||
dfs(node.right, currSum, path);
|
||
|
||
prefixSum[currSum]--;
|
||
if (prefixSum[currSum] === 0) delete prefixSum[currSum];
|
||
path.pop();
|
||
}
|
||
dfs(root, 0, []);
|
||
steps.push({stage:'done', hl:{}, msg:`满足条件的路径数 = ${count}`, prefixSum:{}, currentSum:0, count, path:[]});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderBinaryTree(root, {highlights: s.hl});
|
||
if (s.path.length > 0) {
|
||
viz += '<div style="margin-top:8px;"><b>路径：</b>' + s.path.join(' → ') + ` 前缀和=${s.currentSum}</div>`;
|
||
}
|
||
let psHtml = '<div style="margin-top:8px;"><b>前缀和：</b>';
|
||
Object.entries(s.prefixSum).forEach(([k,v]) => { psHtml += `<code>${k}:${v}</code> `; });
|
||
psHtml += '</div>';
|
||
viz += psHtml;
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.count > 0) {
|
||
$('detailContent').innerHTML += `<div class="current-answer">路径总数：<b>${s.count}</b></div>`;
|
||
}
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">路径总和 III = <b>${s.count}</b> 条</div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','visit→访问','found→找到','add_prefix→加前缀和','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[10,5,-3,3,2,null,11,3,-2,null,1], target=8';
|
||
buildSteps(examples[0].tree, examples[0].target);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
const m = $('inputArea').value.match(/\[([^\]]+)\].*target\s*=\s*(-?\d+)/);
|
||
if (!m) { alert('格式: [10,5,-3,...], target=8'); return; }
|
||
const arr = JSON.parse('['+m[1]+']'); const t = parseInt(m[2]);
|
||
buildSteps(arr, t); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree) + ', target=' + e.target;
|
||
buildSteps(e.tree, e.target); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def pathSum(root, targetSum):
|
||
from collections import defaultdict
|
||
prefix = defaultdict(int)
|
||
prefix[0] = 1
|
||
count = 0
|
||
def dfs(node, curr):
|
||
nonlocal count
|
||
if not node: return
|
||
curr += node.val
|
||
count += prefix[curr - targetSum]
|
||
prefix[curr] += 1
|
||
dfs(node.left, curr)
|
||
dfs(node.right, curr)
|
||
prefix[curr] -= 1
|
||
dfs(root, 0)
|
||
return count`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_lowest_common_ancestor_of_a_binary_tree():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [3,5,1,6,2,0,8,null,null,7,4], p: 5, q: 1, label: '示例1: p=5, q=1 → LCA=3'},
|
||
{tree: [3,5,1,6,2,0,8,null,null,7,4], p: 5, q: 4, label: '示例2: p=5, q=4 → LCA=5'},
|
||
];
|
||
let root, steps, stepCtrl, pVal, qVal, lcaVal;
|
||
|
||
function findNodeByVal(node, val) {
|
||
if (!node) return null;
|
||
if (node.val === val) return node;
|
||
return findNodeByVal(node.left, val) || findNodeByVal(node.right, val);
|
||
}
|
||
|
||
function buildSteps(arr, p, q) {
|
||
root = arrayToTree(arr); pVal = p; qVal = q;
|
||
steps = []; lcaVal = null;
|
||
const pNode = findNodeByVal(root, p);
|
||
const qNode = findNodeByVal(root, q);
|
||
const targetHl = {};
|
||
if (pNode) targetHl[pNode._id] = 'active';
|
||
if (qNode) targetHl[qNode._id] = 'active';
|
||
|
||
steps.push({stage:'init', hl:Object.assign({}, targetHl), msg:`寻找 ${p} 和 ${q} 的最近公共祖先`});
|
||
|
||
function dfs(node) {
|
||
if (!node) return null;
|
||
steps.push({stage:'enter', hl:Object.assign({[node._id]:'current'}, targetHl), msg:`进入节点 ${node.val}`});
|
||
|
||
if (node.val === p || node.val === q) {
|
||
steps.push({stage:'found', hl:{[node._id]:'current'}, msg:`节点 ${node.val} 是目标节点 ${node.val===pVal?'p':'q'}！`});
|
||
return node;
|
||
}
|
||
|
||
const left = dfs(node.left);
|
||
const right = dfs(node.right);
|
||
|
||
if (left && right) {
|
||
lcaVal = node.val;
|
||
steps.push({stage:'lca', hl:{[node._id]:'current'}, msg:`左右子树各找到一个目标，LCA = ${node.val}`, lca:node.val});
|
||
return node;
|
||
}
|
||
const ret = left || right;
|
||
if (ret) {
|
||
steps.push({stage:'return_one', hl:{[node._id]:'visited'}, msg:`节点 ${node.val}：一侧找到目标，向上返回`});
|
||
} else {
|
||
steps.push({stage:'return_none', hl:{[node._id]:'visited'}, msg:`节点 ${node.val}：两侧都没找到，返回 null`});
|
||
}
|
||
return ret;
|
||
}
|
||
dfs(root);
|
||
steps.push({stage:'done', hl:{}, msg:`最近公共祖先 = ${lcaVal !== null ? lcaVal : 'null'}`, lca:lcaVal});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderBinaryTree(root, {highlights: s.hl});
|
||
viz += `<div style="margin-top:8px;font-size:14px;">p = <b style="color:var(--blue);">${pVal}</b> q = <b style="color:var(--purple);">${qVal}</b></div>`;
|
||
$('vizArea').innerHTML = viz;
|
||
$('detailContent').innerHTML = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">LCA(${pVal}, ${qVal}) = <b>${s.lca}</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','enter→进入','found→找到目标','lca→确定LCA','return_one→返回一侧','return_none→返回空','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[3,5,1,6,2,0,8,null,null,7,4], p=5, q=1';
|
||
buildSteps(examples[0].tree, examples[0].p, examples[0].q);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
const m = $('inputArea').value.match(/\[([^\]]+)\].*p\s*=\s*(-?\d+).*q\s*=\s*(-?\d+)/);
|
||
if (!m) { alert('格式: [3,5,1,...], p=5, q=1'); return; }
|
||
const arr = JSON.parse('['+m[1]+']');
|
||
buildSteps(arr, parseInt(m[2]), parseInt(m[3]));
|
||
stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree) + `, p=${e.p}, q=${e.q}`;
|
||
buildSteps(e.tree, e.p, e.q); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def lowestCommonAncestor(root, p, q):
|
||
if not root or root == p or root == q:
|
||
return root
|
||
left = lowestCommonAncestor(root.left, p, q)
|
||
right = lowestCommonAncestor(root.right, p, q)
|
||
if left and right:
|
||
return root
|
||
return left if left else right`, {lang:'Python'});
|
||
'''
|
||
|
||
def js_binary_tree_maximum_path_sum():
|
||
return _TREE_UTILS + r'''
|
||
const examples = [
|
||
{tree: [-10,9,20,null,null,15,7], label: '示例1: [-10,9,20,null,null,15,7] → 42'},
|
||
{tree: [2,-1], label: '示例2: [2,-1] → 2'},
|
||
{tree: [-3], label: '示例3: [-3] → -3'},
|
||
];
|
||
let root, steps, stepCtrl;
|
||
|
||
function buildSteps(arr) {
|
||
root = arrayToTree(arr);
|
||
steps = [];
|
||
let maxSum = -Infinity;
|
||
|
||
steps.push({stage:'init', hl:{}, msg:'DFS 返回节点最大贡献，维护全局最大路径和', maxSum: null});
|
||
|
||
function dfs(node) {
|
||
if (!node) return 0;
|
||
steps.push({stage:'enter', hl:{[node._id]:'current'}, msg:`进入节点 ${node.val}`, maxSum});
|
||
|
||
const leftGain = Math.max(0, dfs(node.left));
|
||
const rightGain = Math.max(0, dfs(node.right));
|
||
|
||
const pathSum = node.val + leftGain + rightGain;
|
||
const oldMax = maxSum;
|
||
if (pathSum > maxSum) maxSum = pathSum;
|
||
const contribution = node.val + Math.max(leftGain, rightGain);
|
||
|
||
steps.push({stage:'calc', hl:{[node._id]:'visited'}, msg:`节点 ${node.val}：左贡献=${leftGain}，右贡献=${rightGain}，路径和=${node.val}+${leftGain}+${rightGain}=${pathSum}，最大${oldMax}→${maxSum}，向上贡献=${contribution}`, maxSum, contribution, leftGain, rightGain, pathSum});
|
||
return contribution;
|
||
}
|
||
if (root) dfs(root);
|
||
else maxSum = 0;
|
||
steps.push({stage:'done', hl:{}, msg:`最大路径和 = ${maxSum}`, maxSum});
|
||
}
|
||
|
||
function render(step) {
|
||
const s = steps[step];
|
||
let viz = renderBinaryTree(root, {highlights: s.hl});
|
||
$('vizArea').innerHTML = viz;
|
||
let detail = '<div class="calc-block">' + s.msg + '</div>';
|
||
if (s.contribution !== undefined) {
|
||
detail += `<div class="current-answer">最大路径和：<b>${s.maxSum}</b>
|
||
<br>向上贡献=${s.contribution} 左=${s.leftGain} 右=${s.rightGain} 路径和=${s.pathSum}</div>`;
|
||
}
|
||
$('detailContent').innerHTML = detail;
|
||
if (s.stage === 'done') {
|
||
$('resultContent').innerHTML = `<div class="final-answer">最大路径和 = <b>${s.maxSum}</b></div>`;
|
||
}
|
||
$('hintText').textContent = s.msg;
|
||
const stages = ['init→初始化','enter→进入','calc→计算','done→完成'];
|
||
$('pipeline').innerHTML = stages.map(st => {
|
||
const [k,l] = st.split('→');
|
||
return `<span class="pipe-step ${s.stage===k?'active':''}">${l}</span>`;
|
||
}).join('<i>→</i>');
|
||
}
|
||
|
||
function init() {
|
||
const sel = $('exampleSelect');
|
||
examples.forEach((e,i) => { sel.innerHTML += `<option value="${i}">${e.label}</option>`; });
|
||
$('inputArea').value = '[-10,9,20,null,null,15,7]';
|
||
buildSteps(examples[0].tree);
|
||
stepCtrl = new StepController({onStep: render});
|
||
stepCtrl.setSteps(steps.map((_,i)=>i));
|
||
$('stepInfo').textContent = '步骤 1 / ' + steps.length;
|
||
stepCtrl.onStep = (idx) => { render(idx); $('stepInfo').textContent = `步骤 ${idx+1} / ${steps.length}`; };
|
||
$('applyBtn').onclick = () => {
|
||
try { const arr = JSON.parse($('inputArea').value); buildSteps(arr); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0); $('stepInfo').textContent = '步骤 1 / ' + steps.length; }
|
||
catch(e) { alert('请输入合法数组'); }
|
||
};
|
||
$('exampleSelect').onchange = () => {
|
||
const e = examples[parseInt($('exampleSelect').value)];
|
||
$('inputArea').value = JSON.stringify(e.tree);
|
||
buildSteps(e.tree); stepCtrl.setSteps(steps.map((_,i)=>i)); render(0);
|
||
};
|
||
$('prevBtn').onclick = () => stepCtrl.prev();
|
||
$('nextBtn').onclick = () => stepCtrl.next();
|
||
$('jumpBtn').onclick = () => stepCtrl.jumpToEnd();
|
||
$('autoBtn').onclick = () => { const on = stepCtrl.toggleAuto(); $('autoBtn').textContent = on ? '暂停' : '自动播放'; };
|
||
$('resetBtn').onclick = () => { stepCtrl.reset(); $('autoBtn').textContent = '自动播放'; };
|
||
}
|
||
init();
|
||
$('codeArea').innerHTML = renderCode(`def maxPathSum(root):
|
||
max_sum = float('-inf')
|
||
def dfs(node):
|
||
nonlocal max_sum
|
||
if not node: return 0
|
||
left = max(0, dfs(node.left))
|
||
right = max(0, dfs(node.right))
|
||
max_sum = max(max_sum, node.val + left + right)
|
||
return node.val + max(left, right)
|
||
dfs(root)
|
||
return max_sum`, {lang:'Python'});
|
||
'''
|
||
|