LeetCode 116-120

116. 填充每个节点的下一个右侧节点指针

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            Node pre = q.peek();
            for (int i = 0; i < size; i++) {
                Node front = q.poll();
                if (front.left != null) {
                    q.offer(front.left);
                }
                if (front.right != null) {
                    q.offer(front.right);
                }
                if (i != 0) {
                    pre.next = front;
                    pre = front;
                }
            }
        }
        return root;
    }
}

117. 填充每个节点的下一个右侧节点指针 II

和第116题代码一模一样

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            Node pre = q.peek();
            for (int i = 0; i < size; i++) {
                Node front = q.poll();
                if (front.left != null) {
                    q.offer(front.left);
                }
                if (front.right != null) {
                    q.offer(front.right);
                }
                if (i != 0) {
                    pre.next = front;
                    pre = front;
                }
            }
        }
        return root;
    }
}

118. 杨辉三角

class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<Integer> getNline(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i == 1 || i == n) {
                list.add(1);
                continue;
            }
            list.add(res.get(n - 2).get(i - 2) + res.get(n - 2).get(i - 1));
        }
        return list;
    }

    public List<List<Integer>> generate(int numRows) {
        for (int i = 1; i <= numRows; i++) {
            res.add(getNline(i));
        }
        return res;
    }
}

119. 杨辉三角 II

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> pre = new ArrayList<>(), cur = new ArrayList<>();
        pre.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = 1; j <= i + 1; j++) {
                if (j == 1 || j == i + 1) {
                    cur.add(1);
                    continue;
                }
                cur.add(pre.get(j - 2) + pre.get(j - 1));
            }
            pre = new ArrayList<>(cur);
            cur.clear();
        }
        return pre;
    }
}

120. 三角形最小路径和

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        int[] pre = new int[len];
        for (int i = 0; i < triangle.get(len - 1).size(); i++) {
            pre[i] = triangle.get(len - 1).get(i);
        }
        for (int i = len - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                pre[j] = Math.min(pre[j], pre[j + 1]) + triangle.get(i).get(j);
            }
        }
        return pre[0];
    }
}