二叉树最长上升子序列

对于一棵二叉树，我们可以定义其最长上升子序列（LIS）为从根节点开始，沿着任意路径向下遍历，使得经过的结点值单调递增的最长路径长度。

为了求解二叉树的 LIS，可以考虑使用动态规划（DP）的方法。具体来说，我们可以定义一个数组 dp，其中 dp[i] 表示以第 i 个结点为结尾的 LIS 长度。对于一个结点 i，其 LIS 长度可以通过枚举其所有子结点 j，如果 val[i] < val[j]，则有转移方程：

dp[i] = max(dp[i], dp[j] + 1)

最终的 LIS 长度即为 dp 数组中的最大值。

下面是一个 Python 代码实现：

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

def longest_increasing_path(root: TreeNode) -> int:
    def dfs(node: TreeNode) -> Tuple[int, int]:
        if not node:
            return 0, 0
        left_len, left_inc = dfs(node.left)
        right_len, right_inc = dfs(node.right)
        cur_len = 1
        if node.left and node.left.val > node.val:
            cur_len = max(cur_len, left_inc + 1)
        if node.right and node.right.val > node.val:
            cur_len = max(cur_len, right_inc + 1)
        cur_inc = 1
        if node.left and node.left.val < node.val:
            cur_inc = max(cur_inc, left_len + 1)
        if node.right and node.right.val < node.val:
            cur_inc = max(cur_inc, right_len + 1)
        return cur_len, cur_inc
    
    return dfs(root)[0]

其中 dfs 函数返回一个元组，第一个元素表示以当前结点为结尾的 LIS 长度，第二个元素表示以当前结点为结尾的 LIS 递减子序列长度。对于每个结点，我们分别计算其向左子树和右子树的 LIS 长度和递减子序列长度，并根据当前结点与子结点之间的大小关系来更新当前结点的 LIS 长度和递减子序列长度。最终返回根节点的 LIS 长度即可。