给定一个二叉树，请你找出其中最长严格递增路径的长度。（提示：使用动态规划）

GeekLiHua

发布于 2025-01-21 08:59:05

8700

代码可运行

文章被收录于专栏：JavaJava

运行总次数：0

代码可运行

给定一个二叉树，请你找出其中最长严格递增路径的长度。（提示：使用动态规划）

简介：给定一个二叉树，请你找出其中最长严格递增路径的长度。（提示：使用动态规划）

算法思路

算法思路：

我们可以对整个二叉树进行一些遍历，采用动态规划的思想来求解最长严格递增路径的长度。具体而言，我们依次计算每个节点作为父节点时所构成的最长严格递增路径长度，并记录下来。

在这里，我们采用一个数组 dp 来存储不同节点下的最长递归路径长度。其中，dp[i] 表示以节点 i 作为结尾的最长递归路径长度。同时，我们需要定义一个函数 dfs(node)，用于计算当前二叉树中以 node 节点作为结尾的最长递增路径的长度，其主要实现如下：

如果节点为空，返回 0；
遍历左子树和右子树，并分别调用 dfs 函数，在这两棵树中找到以 left 和 right 结尾的最长递增路径长度；
如果左子树中节点值大于该节点值，则 left 加上 1；否则，left 置为 0；
同理，如果右子树中节点值大于该节点值，则 right 加上 1；否则，right 置为 0；
更新 dp[node] 的值，并返回 left 或 right 中的较大值加 1。

下面是 C++ 实现的代码，每行都添加了详细注释：

#include <iostream>
#include <algorithm> // 使用 c++ 中的 max() 函数

using namespace std;

// 定义二叉树节点类
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int longestIncreasingPath(TreeNode* root) { // 求解最长递增路径长度
        if (!root) return 0; // 如果二叉树为空，返回 0

        int res = 1; // 记录最大路径长度
        dfs(root, res); // 计算最大路径长度

        return res; // 返回结果
    }

    int dfs(TreeNode* node, int& res) { // 计算节点作为父节点时的最大路径长度
        if (!node) return 0; // 如果该节点为空，返回 0

        // 计算左右子树中以其作为结尾的、连续严格递增的序列长度
        int left = dfs(node->left, res);
        int right = dfs(node->right, res);

        left = (node->left && node->left->val < node->val) ? left + 1 : 0; // 根据节点值判断更新 left
        right = (node->right && node->right->val < node->val) ? right + 1 : 0; // 根据节点值判断更新 right

        res = max(res, left + right); // 更新整个树中最大路径长度
        return max(left, right) + 1; // 返回以该节点作为结尾的最大路径长度
    }
};

int main() {
    // 创建一棵二叉树
    TreeNode* root = new TreeNode(1);
    TreeNode* node1 = new TreeNode(2);
    TreeNode* node2 = new TreeNode(3);
    TreeNode* node3 = new TreeNode(4);
    TreeNode* node4 = new TreeNode(5);

    root->left = node1;
    node1->left = node2;
    node1->right = node3;
    node3->right = node4;

    Solution s;
    int res = s.longestIncreasingPath(root); // 求解最长递增路径长度

    cout << res << endl; // 输出结果

    return 0;
}

在上述代码实现中，我们定义了一个类 Solution 来表示对于二叉树的处理操作。其成员函数包括：

longestIncreasingPath：用于计算最长递增城市的长度；
dfs：用于遍历整个二叉树，并计算出节点所构建的最长递增路径长度。

最终的结果可以在 dfs 函数中返回，我们还定义了一个 TreeNode 结构体来表示二叉树节点。

Java版本

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

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public int longestIncreasingPath(TreeNode root) { // 求解最长递增路径长度
        if (root == null) return 0; // 如果二叉树为空，返回 0

        int[] max = new int[]{1}; // 数组用于存储最大路径长度
        dfs(root, max); // 计算最大路径长度

        return max[0]; // 返回结果
    }

    private int dfs(TreeNode node, int[] max) { // 计算节点作为父节点时的最大路径长度
        if (node == null) return 0; // 如果该节点为空，返回 0

        // 计算左右子树中以其作为结尾的、连续严格递增的序列长度
        int left = dfs(node.left, max);
        int right = dfs(node.right, max);

        left = (node.left != null && node.left.val < node.val) ? left + 1 : 0; // 根据节点值判断更新 left
        right = (node.right != null && node.right.val < node.val) ? right + 1 : 0; // 根据节点值判断更新 right

        max[0] = Math.max(max[0], left + right); // 更新整个树中最大路径长度
        return Math.max(left, right) + 1; // 返回以该节点作为结尾的最大路径长度
    }
}

public class Main {
    public static void main(String[] args) {
        // 创建一棵二叉树
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(5);

        root.left = node1;
        node1.left = node2;
        node1.right = node3;
        node3.right = node4;

        Solution s = new Solution();
        int res = s.longestIncreasingPath(root); // 求解最长递增路径长度

        System.out.println(res); // 输出结果
    }
}