Leetcode做题记录

• 树
• • 二叉树
  • • 剑指 Offer 32 - I 从上到下打印二叉树
• 链表
• • • 725. 分隔链表

############################################################################################

题目：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

思路：利用队列queue先进先出的特点，从root开始，每次poll出一个node，res中添加这个node 的val，然后再add它的左右节点。重复上述步骤，由于queue是先进先出的，因此这样就可以从左到右逐个添加

JAVA：

class Solution {
    public int[] levelOrder(TreeNode root) {
        Queue queue = new linkedList<>();//利用linkedList建一个空的队列
        if(root == null){
            return new int[0];
        }
        queue.add(root);//queue首先添加root进去
        ArrayList tmp = new ArrayList<>();//用ArrayList方便添加，最后再转成int[]

        //核心过程
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            tmp.add(node.val);
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }

        //将输出格式变为int[]
        int length = tmp.size();
        int[] res = new int[length];//初始化：length个0的list
        for(int i=0; i 
Python3：
 
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        queue = collections.deque()
        res = []
        if not root:
            return []
        queue.append(root)
        while queue:
            node = queue.popleft()#由于下面deque的append是从右边添加，如果要做到先进先出，就要从左边pop。这里如果直接用pop是默认从右边pop
            res.append(node.val)
            if node.left:
                queue.append(node.left)#从右边添加
            if node.right:
                queue.append(node.right)
        return res
 
 
链表 
############################################################################################
 
725. 分隔链表 
题目：
 
 思路：要求将一个链表分割为k份，且前面的部分长度应大于等于后面的部分，并且任意两部分的长度差不能超过1。因此前面 N%k 个片段的长度为|N/k|+1，后面 k-N%k 个片段的长度为|N/k|
 
JAVA：
 
//要求将一个链表分割为k份，且前面的部分长度应大于等于后面的部分，并且任意两部分的长度差不能超过1
//思路：前面 N%k 个片段的长度为|N/k|+1，后面 k-N%k 个片段的长度为|N/k|
class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        //目前有链表的头，首先遍历链表，获得链表的长度N
        int N = 0;
        ListNode tmp = head;
        //tmp从head开始不断后移，直到末尾(末尾节点的next是null)
        while(tmp != null){//这里不能用tmp.next != null，否则当tmp指到最后一个节点时，就已经满足条件，这时N就比实际长度少1
            N++;
            tmp = tmp.next;
        }

        int length = N/k;
        int remainder = N%k;

        //初始化一个由k个ListNode构成的变量result，然后往里面放截取的k段序列，最后return这个result即可
        ListNode[] result = new ListNode[k];
        ListNode curr = head;
        
        //每一次，result的一个序列都跟随curr从起点运动到终点
        for(int i = 0; i < k && curr != null; i++){
            result[i] = curr;
            int part_len = length + (i 
Python3：
 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:
        len = 0
        tmp = head
        while tmp:#这里可以直接用tmp，因为python默认所有非零或null的量为True，JAVA不行因为JAVA不支持这种转化
            len += 1
            tmp = tmp.next
        
        each_len = len//k#len/k是float值，len//k才是取整
        remainder = len%k

        result = [None for _ in range(k)]#这里首先要建k个占位符，因为有可能后面几个集都是空的
        curr = head
        i = 0
        while i