"""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'});
'''