题解 | 山峰间的极限跳跃

一、解题思路：

本题是典型的二叉树动态规划问题，可通过深度优先搜索方法解决。

易错点：

1、题目要求在整个二叉树中找到最长路径，而不是从根节点开始的最长路径；

2、题目要求一个完整的路径，必须从上往下、子节点严格交替；

3、二叉树的数据按照它的前序遍历输入，题目同时给出了当前节点和左右子节点的信息，可以通过这点构造整个二叉树；

整体思路：

1、首先解析输入的数据，通过指针数组存放每个节点的指针，再通过一个build函数构造整个二叉树；

2、DFS遍历过程中，假设当前节点是最长路径的起点，从该节点出发有两种可能：走向下一个海拔更高或海拔更低的节点。因此我们需要分别计算从当前节点开始，第一步走向更高或者第一步走向更低的路径长度；

3、构造DFS函数。首先，每个节点自身算一条长度为1的路径；其次，如果下一个节点满足了“极限跳跃”的条件，说明当前节点的路径可以拓展，我们可以得出以下结论：

用dp[i][0]和dp[idx][1]分别表示从idx出发，第一步上升或下降的最长路径。

1. base case: 从当前节点root->idx出发，上升和下降的初始值都为1；
2. 检查子节点是否满足“极限跳跃”，条件满足则更新dp[root->idx][0]或dp[root->idx][1]；
3. 如果从当前节点到子节点是上升，从子节点再到下一步只能下降：dp[root->idx][0] = dp[root->next->idx][1] + 1
4. 如果从当前节点到子节点是下降，从子节点再到下一步只能上升：dp[root->idx][1] = dp[root->next->idx][0] + 1

4、实际上，DFS函数从最底层的子节点开始，向上遍历所有节点，并维护了一个二维数组dp[MAX_NUM][2]，其中存放了以某个节点为起始位置、第一步向上或向下的最长“极限跳跃”路径。在外部增加一个变量MAX_LEN，每次DFS遍历完一个节点时更新MAX_LEN的值，最后就可以得到最长路径。

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define max(a,b) ((a) > (b)) ? (a) : (b)
#define MAX_NODES 10000

struct TreeNode {
    int val; // 节点的值
    int idx; // 节点的下标
    struct TreeNode* left;
    struct TreeNode* right;
};

int MAX_LEN = 0; // 最终返回的答案
int LIMIT = 0;   // 极限跳跃阈值
int dp[MAX_NODES][2]; // DFS维护的二维数组

void dfs(struct TreeNode* root) {
    if (!root)
        return;
    // base case
    dp[root->idx][0] = 1;
    dp[root->idx][1] = 1;

    if (root->left) {
        dfs(root->left);

        int val_l = root->left->val;
        int val_cur = root->val;
        int idx_l = root->left->idx;

        if ((val_l - val_cur) >= LIMIT) {
            dp[root->idx][0] = max(dp[root->idx][0], dp[idx_l][1] + 1);
        }

        if ((val_cur - val_l) >= LIMIT) {
            dp[root->idx][1] = max(dp[root->idx][1], dp[idx_l][0] + 1);
        }
    }

    if (root->right) {
        dfs(root->right);

        int val_r = root->right->val;
        int val_cur = root->val;
        int idx_r = root->right->idx;

        if ((val_r - val_cur) >= LIMIT) {
            dp[root->idx][0] = max(dp[root->idx][0], dp[idx_r][1] + 1);
        }

        if ((val_cur - val_r) >= LIMIT) {
            dp[root->idx][1] = max(dp[root->idx][1], dp[idx_r][0] + 1);
        }
    }

    MAX_LEN = max(MAX_LEN, dp[root->idx][0]);
    MAX_LEN = max(MAX_LEN, dp[root->idx][1]);
}

struct TreeNode* build(struct TreeNode** nodeSet, int** nodeMsg, int* nodeNums, int* curNum) {
    if (*curNum >= *nodeNums)
        return NULL;
    
    int cur = *curNum;
    *curNum += 1;
    // 按照先序遍历顺序，依次构造当前节点的左右子节点
    struct TreeNode *tmp = nodeSet[cur];
    if (nodeMsg[cur][0] == -1) {
        tmp->left = NULL;
    } else {
        tmp->left = build(nodeSet, nodeMsg, nodeNums, curNum);
    }

    if (nodeMsg[cur][1] == -1) {
        tmp->right = NULL;
    } else {
        tmp->right = build(nodeSet, nodeMsg, nodeNums, curNum);
    }
    
    return tmp;
}

int main() {
    int nums;
    int cur, left, right;

    scanf("%d %d", &nums, &LIMIT);

    struct TreeNode** nodeSet = malloc(sizeof(struct TreeNode*)*nums);
    int **nodeMsg = malloc(sizeof(int*)*nums);
    int setNums = 0;
    while (scanf("%d %d %d", &cur, &left, &right) != EOF) {
        // 存储所有二叉树的节点
        nodeSet[setNums] = malloc(sizeof(struct TreeNode));
        memset(nodeSet[setNums], 0, sizeof(struct TreeNode));
        nodeSet[setNums]->val = cur;
        nodeSet[setNums]->idx = setNums;
        // 存储所有二叉树节点的左右子节点信息
        nodeMsg[setNums] = malloc(sizeof(int)*2);
        nodeMsg[setNums][0] = left;
        nodeMsg[setNums][1] = right;
        setNums++;
    }

    // 构造二叉树
    int curNode = 0;
    struct TreeNode *root = build(nodeSet, nodeMsg, &setNums, &curNode);

    dfs(root);

    // 释放内存
    for (int i = 0; i < setNums; i++) {
        free(nodeSet[i]);
        nodeSet[i] = NULL;
        free(nodeMsg[i]);
        nodeMsg[i] = NULL;
    }
    free(nodeSet);
    nodeSet = NULL;
    free(nodeMsg);
    nodeMsg = NULL;

    printf("%d\n", MAX_LEN);
    return 0;
}