二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内

• -100 <= Node.val <= 100

解题思路

递归

这段代码是用Java实现的二叉树的中序遍历（Inorder Traversal），采用递归的方法。中序遍历的顺序是：左子树 → 根节点 → 右子树。

1. 主方法 inorderTraversal

public List<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList();
    doInorderTraversal(root, result);
    return result;
}

• 创建一个空的ArrayList用于存储遍历结果

• 调用辅助方法doInorderTraversal进行实际遍历

• 返回存储结果的列表

2. 递归辅助方法 doInorderTraversal

public void doInorderTraversal(TreeNode root, ArrayList<Integer> result) {
    if(root == null){
        return;
    }
    
    doInorderTraversal(root.left, result);  // 遍历左子树
    result.add(root.val);                  // 访问根节点
    doInorderTraversal(root.right, result); // 遍历右子树
}

• 基线条件：如果当前节点为null，直接返回（递归终止条件）

• 递归过程：

  1. 先递归遍历左子树

  2. 将当前节点的值加入结果列表

  3. 然后递归遍历右子树

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
       ArrayList<Integer> result = new ArrayList();
       doInorderTraversal(root,result);
       return result;
    }

    public void doInorderTraversal(TreeNode root,ArrayList<Integer> result) {
        if(root == null){
            return;
        }

        doInorderTraversal(root.left,result);
        result.add(root.val);
        doInorderTraversal(root.right,result);

    }
}

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500

• -104 <= nums[i] <= 104

解题思路（动态规划算法）

这段代码实现了求解最长递增子序列(LIS)长度的动态规划算法。下面我将详细解析其逻辑：

基本思路

• 使用动态规划数组dp，其中dp[i]表示以nums[i]结尾的最长递增子序列长度

• 通过双重循环比较元素，逐步构建dp数组

• 最终返回dp数组中的最大值

代码逻辑分解

1. 初始化

int[] dp = new int[nums.length];
int maxmax = 0;

• dp数组初始化为全0，因为每个元素自身至少构成长度为1的子序列

• maxmax用于记录全局最大值

2. 外层循环

for (int i = 1; i < nums.length; i++)

• 从第2个元素开始遍历数组（因为第一个元素的LIS长度就是1）

3. 内层循环

for (int j = 0; j < i; j++)

• 对于每个nums[i]，检查它之前的所有元素nums[j]

4. 状态转移

if (nums[j] < nums[i]) {
    dp[i] = Math.max(dp[i], dp[j] + 1);
}

• 如果nums[j] < nums[i]，说明nums[i]可以接在nums[j]后面形成更长的递增子序列

• 更新dp[i]为dp[j]+1和当前dp[i]中的较大值

5. 更新全局最大值

maxmax = Math.max(dp[i], maxmax);

• 每次更新dp[i]后，同步更新全局最大值

6. 返回结果

return maxmax + 1;

• 因为dp数组初始值为0，所以最终结果需要加1

示例分析

以输入[10,9,2,5,3,7,101,18]为例：

最终返回maxmax + 1 = 4，对应子序列[2,3,7,101]

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int maxmax = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxmax = Math.max(dp[i], maxmax);
        }
        return maxmax + 1;
    }
}