二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

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

示例 3：

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

解题思路

代码实现了二叉树的层次遍历（Level Order Traversal），使用递归的方式完成。让我为您详细梳理逻辑：

代码逻辑梳理

1. 主方法 levelOrder

public List<List<Integer>> levelOrder(TreeNode root) {
    if(root == null){                    // 处理空树情况
        return new ArrayList();
    }
    ArrayList<List<Integer>> all = new ArrayList();  // 存储所有层的结果
    ArrayList<Integer> sub1 = new ArrayList();       // 第一层
    sub1.add(root.val);                  // 添加根节点值
    all.add(sub1);                       // 将第一层加入结果集
    
    // 准备第二层的节点
    ArrayList<TreeNode> sub = new ArrayList();
    if (root.left != null) {
        sub.add(root.left);
    }
    if (root.right != null) {
        sub.add(root.right);
    }
    
    doLevelOrder(all, sub);              // 递归处理后续层次
    return all;
}

2. 递归方法 doLevelOrder

public void doLevelOrder(ArrayList<List<Integer>> all, ArrayList<TreeNode> sub) {
    if (sub == null || sub.isEmpty()) {  // 递归终止条件：当前层为空
        return;
    }

    ArrayList<TreeNode> ssub = new ArrayList<>();  // 存储下一层的节点
    ArrayList<Integer> sub1 = new ArrayList();     // 存储当前层的值
    
    for (TreeNode treeNode : sub) {      // 遍历当前层所有节点
        sub1.add(treeNode.val);          // 记录当前节点的值
        
        // 将子节点加入下一层
        if (treeNode.left != null) {
            ssub.add(treeNode.left);
        }
        if (treeNode.right != null) {
            ssub.add(treeNode.right);
        }
    }

    all.add(sub1);                       // 将当前层加入结果集
    doLevelOrder(all, ssub);             // 递归处理下一层
}

执行流程示例

以二叉树 [3,9,20,null,null,15,7] 为例：

    3
   / \
  9  20
    /  \
   15   7

执行过程：

levelOrder开始:
  all = [] → 添加第一层 [3] → all = [[3]]
  sub = [9, 20] (第二层节点)

doLevelOrder第一次调用:
  当前层sub = [9, 20]
  遍历节点9: sub1添加9, ssub添加(无子节点)
  遍历节点20: sub1添加20, ssub添加[15, 7]
  all添加[9, 20] → all = [[3], [9, 20]]
  递归调用doLevelOrder(all, [15, 7])

doLevelOrder第二次调用:
  当前层sub = [15, 7]
  遍历节点15: sub1添加15, ssub添加(无子节点)
  遍历节点7: sub1添加7, ssub添加(无子节点)
  all添加[15, 7] → all = [[3], [9, 20], [15, 7]]
  递归调用doLevelOrder(all, []) → 终止

返回结果: [[3], [9, 20], [15, 7]]

完整代码：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList();
        }
        ArrayList<List<Integer>> all = new ArrayList();
        ArrayList<Integer> sub1 = new ArrayList();
        sub1.add(root.val);
        all.add(sub1);
        ArrayList<TreeNode> sub = new ArrayList();
        if (root.left != null) {
            sub.add(root.left);
        }
        if (root.right != null) {
            sub.add(root.right);
        }
        doLevelOrder(all, sub);
        return all;

    }

    public void doLevelOrder(ArrayList<List<Integer>> all, ArrayList<TreeNode> sub) {

        if (sub == null || sub.isEmpty()) {
            return;
        }

        ArrayList<TreeNode> ssub = new ArrayList<>();
        ArrayList<Integer> sub1 = new ArrayList();
        for (TreeNode treeNode : sub) {
            sub1.add(treeNode.val);

            if (treeNode.left != null) {
                ssub.add(treeNode.left);
            }
            if (treeNode.right != null) {
                ssub.add(treeNode.right);
            }
        }

all.add(sub1);
        doLevelOrder(all, ssub);

    }
}

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 105

• -231 <= nums[i] <= 231 - 1

• 0 <= k <= 105

解题思路（额外数组空间两段复制）

1. 参数处理与边界条件

int[] newNums = new int[nums.length];  // 创建新数组存放结果
int a = k;
if (k > nums.length) {
    a = k % nums.length;  // 处理k大于数组长度的情况
}
if (a == 0) {             // 如果旋转步数为0，直接返回
    return;
}

关键点：

• 当 k > nums.length 时，实际有效旋转步数是 k % nums.length

2. 计算分割点

int mid = nums.length - a;  // 计算分割位置

意义： mid 表示原数组中不需要移动的部分的起始位置

3. 两段复制过程

// 第一阶段：复制后半部分（需要移到前面的元素）
int i = 0;
int aa = mid;
while (aa < nums.length) {
    newNums[i++] = nums[aa++];  // 将原数组后半部分放到新数组前面
}

// 第二阶段：复制前半部分（需要移到后面的元素）
int j = 0;
while (j < mid) {
    newNums[i++] = nums[j++];   // 将原数组前半部分放到新数组后面
}

4. 结果回写

for (int h = 0; h < nums.length; h++) {
    nums[h] = newNums[h];  // 将新数组内容复制回原数组
}

完整代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        		HashSet<ListNode> objects = new HashSet<>();
		while (head != null && !objects.contains(head)) {
			objects.add(head);
			head = head.next;
		}
		return head;
    }
}