题解 | #山峰间的极限跳跃#

山峰间的极限跳跃

https://www.nowcoder.com/practice/5ac155b3af454f4f9d74a5a5423bf61b

REALHW78 山峰间的极限跳跃

题目链接

山峰间的极限跳跃

题目描述

您是一位极限运动家，正挑战一片由计算机生成的、结构奇特的数字山脉。

这片山脉由 $N$ 个山峰组成，每个山峰都有其独特的海拔高度。您的目标是规划出一条最长的、符合“极限跳跃”规则的下山路径。

这片数字山脉的结构可以用一棵二叉树来精确描述。您规划的路径必须遵循一系列严格的规则，我们称之为一条“极限交替路径”：

路径方向：路线必须严格自上而下，即只能从一个山峰移动到与之直接相连的子山峰。
严格交替：路径上海拔的变化必须是严格的交替上升和下降。例如，一条合法的路径可以是海拔 $p_1 < p_2 > p_3 < p_4 \dots$ ，其海拔序列满足 $p_1 < p_2, p_2 > p_3, p_3 < p_4$ 。无论是“先升后降”还是“先降后升”的交替模式都是允许的。
极限跳跃：每次移动（从一个山峰到下一个）的海拔绝对差值必须大于或等于一个给定的阈值 $k$ 。形式化地，对于路径上任意相邻的两个山峰 $p_i$ 和 $p_{i+1}$ ，必须满足 $|p_i - p_{i+1}| \ge k$ 。

您的任务是找出在这片山脉中，能够规划出的最长“极限交替路径”的长度。路径的长度以其所包含的山峰数量计算。

输入描述:

第一行包含两个整数 $N$ 和 $k$ 。 $N$ 是山峰的总数, $1 \le N \le 50000$ 。 $k$ 是要求的最小海拔差 (极限跳跃阈值), $0 \le k \le 10^9$ 。

接下来的 $N$ 行描述了山脉的结构。每行包含三个整数 $p, l, r$ ： $p$ 是当前山峰的海拔。 $l$ 是其左侧子山峰的海拔。 $r$ 是其右侧子山峰的海拔。如果某个子山峰不存在，则用 $-1$ 表示。所有山峰的海拔高度都在 $[0, 10^9]$ 范围内，且保证互不相同。

这 $N$ 行的输入顺序遵循该山脉地图的先序遍历顺序。

输出描述:

一个整数，代表最长“极限交替路径”的长度。

解题思路

本题要求在二叉树中寻找满足特定条件的最长路径。这是一个典型的树上动态规划（Tree DP）问题，可以通过深度优先搜索（DFS）来解决。

1. 核心思想

对于树中的任意一个节点 u，最长的有效路径可能从这里开始，也可能经过这里。我们需要计算从 u 出发，并且满足交替升降规则的最长路径。由于路径是交替的，从 u 出发的第一步有两种可能：

走向一个海拔更高的子节点（上升）。
走向一个海拔更低的子节点（下降）。

因此，我们的 DFS 函数对于每个节点 u，需要计算并返回这两个值：

longest_up: 从 u 出发，第一步是上升的最长交替路径长度。
longest_down: 从 u 出发，第一步是下降的最长交替路径长度。

2. 状态转移

在 dfs(u) 的计算过程中：

基础情况: 任何一个节点自身都可以看作是一条长度为 1 的路径。因此，longest_up 和 longest_down 的初始值都为 1。
递归计算: 遍历 u 的每个子节点 v：
- 首先，检查跳跃是否满足“极限”条件：abs(u.val - v.val) >= k。如果不满足，则无法从 u 跳到 v，直接跳过。
- 如果满足条件，我们就可以利用从 v 计算得到的结果来更新 u 的结果：
  - 如果 v.val > u.val（从 u 到 v 是上升）：这意味着 u 的 longest_up 路径可以被拓展。从 u 上升到 v 之后，下一步必须是下降。因此，新的路径长度为 1 + dfs(v).longest_down。我们用这个值来更新 u 的 longest_up。
  - 如果 v.val < u.val（从 u 到 v 是下降）：同理，u 的 longest_down 路径可以被拓展。从 u 下降到 v 之后，下一步必须是上升。因此，新的路径长度为 1 + dfs(v).longest_up。我们用这个值来更新 u 的 longest_down。
全局最长路径: 由于最长路径可以从树中的任何节点开始，我们需要一个全局变量 max_len。在每次计算完一个节点 u 的 longest_up 和 longest_down 之后，都用它们来更新 max_len。

3. 具体实现

树的重建:
- 输入是按先序遍历给出的。我们可以先读取所有 $N$ 行的节点信息（p, l, r）。
- 使用一个 map（或哈希表）来存储每个海拔值到其对应节点的指针/对象的映射。
- 再次遍历读取的信息，利用 map 找到对应的左右子节点，完成树的链接。
- 先序遍历的第一个节点就是树的根节点。
DFS 执行:
- 从根节点开始调用 DFS 函数。
- DFS 函数递归地进行后序遍历（先访问子节点，再处理当前节点），以确保在计算父节点时，其所有子节点的结果已经可用。
- 最终，全局变量 max_len 中存储的就是问题的答案。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

// 树节点定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 全局变量，记录最长路径
int max_len = 0;
// 极限跳跃阈值
int k;

// DFS函数，返回一个pair，分别表示从当前节点出发，
// 第一步向上和向下的最长交替路径长度
pair<int, int> dfs(TreeNode* node) {
    if (!node) {
        return {0, 0};
    }

    // longest_up: 第一步向上走的最长路径
    // longest_down: 第一步向下走的最长路径
    // 初始为1，代表节点自身
    int longest_up = 1;
    int longest_down = 1;

    // 处理左子树
    if (node->left) {
        pair<int, int> left_res = dfs(node->left);
        // 检查是否满足极限跳跃条件
        if (abs(node->val - node->left->val) >= k) {
            if (node->left->val > node->val) { // 向上走
                longest_up = max(longest_up, 1 + left_res.second);
            } else { // 向下走
                longest_down = max(longest_down, 1 + left_res.first);
            }
        }
    }

    // 处理右子树
    if (node->right) {
        pair<int, int> right_res = dfs(node->right);
        // 检查是否满足极限跳跃条件
        if (abs(node->val - node->right->val) >= k) {
            if (node->right->val > node->val) { // 向上走
                longest_up = max(longest_up, 1 + right_res.second);
            } else { // 向下走
                longest_down = max(longest_down, 1 + right_res.first);
            }
        }
    }

    // 更新全局最长路径
    max_len = max({max_len, longest_up, longest_down});

    return {longest_up, longest_down};
}


int main() {
    int n;
    cin >> n >> k;

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    // 存储节点信息 (p -> {l, r})
    map<int, pair<int, int>> node_info;
    // 存储所有节点的海拔，用于创建节点
    vector<int> altitudes;
    // 存储输入的顺序，第一个是根节点
    vector<vector<int>> input_data(n, vector<int>(3));

    for (int i = 0; i < n; ++i) {
        int p, l, r;
        cin >> p >> l >> r;
        node_info[p] = {l, r};
        altitudes.push_back(p);
        input_data[i] = {p, l, r};
    }

    // 创建所有节点
    map<int, TreeNode*> nodes;
    nodes[-1] = nullptr; // -1 代表空节点
    for (int alt : altitudes) {
        nodes[alt] = new TreeNode(alt);
    }

    // 链接节点
    for (auto const& [p, children] : node_info) {
        nodes[p]->left = nodes[children.first];
        nodes[p]->right = nodes[children.second];
    }
    
    // 获取根节点
    TreeNode* root = nodes[input_data[0][0]];
    
    // 开始DFS
    dfs(root);

    cout << max_len << endl;

    return 0;
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class Main {
    static int maxLen = 0;
    static int k;

    // 返回一个大小为2的数组: {longest_up, longest_down}
    private static int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }

        int longestUp = 1;
        int longestDown = 1;

        // 处理左子树
        if (node.left != null) {
            int[] leftRes = dfs(node.left);
            if (Math.abs(node.val - node.left.val) >= k) {
                if (node.left.val > node.val) { // 向上
                    longestUp = Math.max(longestUp, 1 + leftRes[1]);
                } else { // 向下
                    longestDown = Math.max(longestDown, 1 + leftRes[0]);
                }
            }
        }

        // 处理右子树
        if (node.right != null) {
            int[] rightRes = dfs(node.right);
            if (Math.abs(node.val - node.right.val) >= k) {
                if (node.right.val > node.val) { // 向上
                    longestUp = Math.max(longestUp, 1 + rightRes[1]);
                } else { // 向下
                    longestDown = Math.max(longestDown, 1 + rightRes[0]);
                }
            }
        }

        maxLen = Math.max(maxLen, Math.max(longestUp, longestDown));
        return new int[]{longestUp, longestDown};
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        k = sc.nextInt();

        if (n == 0) {
            System.out.println(0);
            return;
        }

        int[][] inputData = new int[n][3];
        Map<Integer, int[]> nodeInfo = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            int p = sc.nextInt();
            int l = sc.nextInt();
            int r = sc.nextInt();
            inputData[i][0] = p;
            inputData[i][1] = l;
            inputData[i][2] = r;
            nodeInfo.put(p, new int[]{l, r});
        }

        Map<Integer, TreeNode> nodes = new HashMap<>();
        nodes.put(-1, null); // -1 代表空节点
        for (int p : nodeInfo.keySet()) {
            nodes.put(p, new TreeNode(p));
        }

        for (Map.Entry<Integer, int[]> entry : nodeInfo.entrySet()) {
            int p = entry.getKey();
            int[] children = entry.getValue();
            TreeNode parentNode = nodes.get(p);
            parentNode.left = nodes.get(children[0]);
            parentNode.right = nodes.get(children[1]);
        }
        
        TreeNode root = nodes.get(inputData[0][0]);
        
        dfs(root);

        System.out.println(maxLen);
    }
}

import sys

# 增加递归深度限制以防 skewed tree
sys.setrecursionlimit(100000)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

max_len = 0
k = 0

def dfs(node):
    """
    返回一个元组 (longest_up, longest_down)
    """
    global max_len
    if not node:
        return 0, 0

    longest_up = 1
    longest_down = 1

    # 处理左子树
    if node.left:
        left_up, left_down = dfs(node.left)
        if abs(node.val - node.left.val) >= k:
            if node.left.val > node.val:  # 向上
                longest_up = max(longest_up, 1 + left_down)
            else:  # 向下
                longest_down = max(longest_down, 1 + left_up)

    # 处理右子树
    if node.right:
        right_up, right_down = dfs(node.right)
        if abs(node.val - node.right.val) >= k:
            if node.right.val > node.val:  # 向上
                longest_up = max(longest_up, 1 + right_down)
            else:  # 向下
                longest_down = max(longest_down, 1 + right_up)

    max_len = max(max_len, longest_up, longest_down)
    return longest_up, longest_down

def solve():
    global k, max_len
    try:
        n, k_val = map(int, input().split())
        k = k_val
    except (IOError, ValueError):
        return

    if n == 0:
        print(0)
        return

    node_info = {}
    input_data = []
    for _ in range(n):
        p, l, r = map(int, input().split())
        node_info[p] = (l, r)
        input_data.append(p)
    
    nodes = {-1: None}
    for p in node_info:
        nodes[p] = TreeNode(p)
        
    for p, children in node_info.items():
        l_alt, r_alt = children
        nodes[p].left = nodes[l_alt]
        nodes[p].right = nodes[r_alt]

    root = nodes[input_data[0]]
    
    dfs(root)
    print(max_len)

solve()

算法及复杂度

算法: 树上动态规划 (Tree DP), 深度优先搜索 (DFS)
时间复杂度: $O(N)$ 。
- 读取输入并建立 map 需要 $O(N \log N)$ 的时间。
- 从 map 重建树结构需要 $O(N \log N)$ 的时间（每次查找子节点）。
- DFS 遍历每个节点一次，所以是 $O(N)$ 。
- 总体时间复杂度为 $O(N \log N)$ ，由树的重建主导。如果使用哈希表（如 C++ 的 unordered_map），则期望时间复杂度为 $O(N)$ 。
空间复杂度: $O(N)$ 。
- 需要 $O(N)$ 的空间来存储节点信息和构建树。
- DFS 的递归栈深度在最坏情况下（链状树）也是 $O(N)$ 。