好的，这是一个关于LCP 26. 导航装置的 TypeScript 实现。这道题的解法基于一个重要的观察。

核心思路：基于“三叉节点”的贪心算法

这道题的关键在于理解“三叉节点”（既有父节点，又有左、右两个子节点的节点）在区分位置时的决定性作用。

对于一个三叉节点，它连接了三个方向：父节点方向、左子树、右子树。如果三个方向中，只有一个方向（或零个方向）有导航装置，那么位于另外两个没有装置方向上的两个景点，到唯一的装置距离可能相同，导致无法区分。因此，为了让位置信息唯一，每个三叉节点的三个方向中，至少要有两个方向拥有导航装置。

基于这个原理，我们可以在DFS过程中采用一个贪心策略：

1. 假设父节点有装置：在进行DFS时，我们暂时假设当前节点的父节点方向已经放置了一个导航装置。
2. 从叶子向根决策：
   • 叶子节点：先不放置装置，返回false（表示该子树内没有装置）。
   • 只有一个子节点的节点：如果它的子节点所在子树已经有一个装置（dfs(child) === true），配合我们假设的“父节点方向有装置”，就有两个装置，足够区分，因此这个节点本身不需要再额外放置装置，返回true。
   • 三叉节点（有左右两个子节点）：这是决策发生的地方。如果它的左、右两个子节点所在子树都“没有”装置（即dfs(left) === false且dfs(right) === false），那么为了满足“至少两个方向有装置”的原则（一个方向假设是父节点），我们必须在其中一个子树上放置一个装置，所以总答案res加1。之后，该节点返回true，表示这个节点下方的子树中，现在已经“有”装置了。
3. 处理根节点：根节点没有父节点，所以之前的“父节点有装置”假设对它是无效的。DFS结束后，需要根据根节点的左右子树情况对答案进行最后修正。变量 s 用于记录这个修正逻辑（具体见代码注释）。

TypeScript 代码实现

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function navigation(root: TreeNode | null): number {
    // res: 统计在DFS过程中决策放置的装置数量
    // s:  记录了离根节点最近的三叉节点的“左右子树是否都有装置”这一状态。
    //     初值设为1，用于处理整棵树是一条链（没有三叉节点）的特殊情况，
    //     因为一条链只需要1个装置就可以区分所有节点。
    let res = 0;
    let s = 1;

    // dfs返回值：boolean
    // true  表示该节点所在的子树中，已经放置了至少一个导航装置
    // false 表示该节点所在的子树中，没有放置任何导航装置
    function dfs(node: TreeNode | null): boolean {
        if (!node) {
            return false; // 空节点，没有装置
        }

        const leftHasDevice = dfs(node.left);
        const rightHasDevice = dfs(node.right);

        // 情况：当前节点是一个三叉节点（有左右两个子节点）
        if (node.left && node.right) {
            // 如果左右子树都没有装置，根据“三叉原则”，必须要在其中一个方向新放一个装置
            // 这里res自增1，代表在某个子树中放置了装置，但不关心具体位置
            if (!leftHasDevice && !rightHasDevice) {
                res++;
            }
            // 更新s的值。如果一个三叉节点的左右子树都“有”装置，
            // 那么对于它的父节点方向来说，它自己本身已经满足“至少两个方向有装置”的条件。
            // 否则，s保持为1，意味着根节点方向可能需要额外装置。
            s = (leftHasDevice && rightHasDevice) ? 0 : 1;
            // 该节点是或将成为其父节点判断中“子树有装置”的来源
            return true;
        }

        // 情况：当前节点只有一个子节点（或为叶子节点）
        // 如果子树中有装置（leftHasDevice || rightHasDevice为true），
        // 配合“父节点方向有装置”的假设，至少有两个方向，所以此处无需新增。
        // 如果子树中无装置，该节点子树也没有装置。
        // 返回左或右子树的装置状态即可。
        return leftHasDevice || rightHasDevice;
    }

    // 对根节点的左右子树分别进行DFS
    const leftHasDevice = dfs(root.left);
    const rightHasDevice = dfs(root.right);

    // 处理根节点的特殊性
    // 如果根节点的左右子树中都“有”装置，那么根节点的两个方向都已经满足条件，无需额外装置。
    // 否则，需要根据s的值来决定是否在根节点位置添加一个装置。
    if (leftHasDevice && rightHasDevice) {
        // 左右子树都有装置，根节点无需再添加
        return res;
    } else {
        // 至少一边子树没有装置，需要补上s个装置（s为0或1）
        return res + s;
    }
}

时间复杂度与空间复杂度

• 时间复杂度：O(N)，其中N是二叉树的节点数。每个节点只被访问一次。
• 空间复杂度：O(N)，在递归过程中，栈的最大深度在最坏情况下（树退化为链表）为O(N)。