1. 重新格式化字符串

给你一个混合了数字和字母的字符串 s，其中的字母均为小写英文字母。

请你将该字符串重新格式化，使得任意两个相邻字符的类型都不同。也就是说，字母后面应该跟着数字，而数字后面应该跟着字母。

请你返回 重新格式化后 的字符串；如果无法按要求重新格式化，则返回一个 空字符串 。

分析：

首先统计s中的数字个数dnum和字母个数anum，当|dnum-anum|<=1时，才可以进行重新格式化。统计完成后如果dnum=anum则其在重新格式化后的字符串中谁占奇数位置谁占偶数位置都可以；如果是不相等则较大的一方占据奇数位置，较小的一方占据偶数位置。

class Solution {
    public String reformat(String s) {
        if (s.length() == 0) return null;
        
        int Dnum = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') Dnum++;
        }
        int Anum = s.length() - Dnum;
        if (Math.abs(Anum - Dnum)>1) return "";
        char[] res = new char[s.length()];
        int a = 0, b = 1;
        if (Anum >= Dnum){
            for (int i = 0; i < s.length(); i++) {
                if (Character.isDigit(s.charAt(i))){
                    res[b] = s.charAt(i);
                    b += 2;
                }else {
                    res[a] = s.charAt(i);
                    a += 2;
                }
            }
        }else {
            for (int i = 0; i < s.length(); i++) {
                if (Character.isDigit(s.charAt(i))){
                    res[a] = s.charAt(i);
                    a += 2;
                }else {
                    res[b] = s.charAt(i);
                    b += 2;
                }
            }
        }
        return new String(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2. 往完全二叉树添加节点

完全二叉树是每一层（除最后一层外）都是完全填充的，并且所有的节点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

• CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构；
• CBTInserter.insert(int v) 向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
• CBTInserter.get_root() 将返回树的根节点。

分析：

使用层序遍历。当初始化该结构时，对输入的root进行层序遍历，当出现节点的左子树或右子树为空时说明该节点为插入操作时的候选节点，把该节点插入到候选队列中去。当调用insert()操作时，把新节点插入到候选队列的第一个节点的子树中，如果插入到了右子树中，则第一个节点要出队；同时不要忘记把新插入的节点放进候选队列中。

class CBTInserter {
    TreeNode root;
    Deque<TreeNode> deque;
    Deque<TreeNode> q;

    public CBTInserter(TreeNode root) {
        this.root = root;
        deque = new ArrayDeque<>();
        q = new ArrayDeque<>();
        deque.addLast(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.pollFirst();
            if (node.left == null || node.right == null) q.addLast(node);
            if (node.left != null) deque.addLast(node.left);
            if (node.right != null) deque.addLast(node.right);
        }
    }

    public int insert(int val) {
        TreeNode node = q.pollFirst();
        if (node.left == null) {
            node.left = new TreeNode(val);
            if (node.right == null) q.addFirst(node);
            q.addLast(node.left);
        } else {
            node.right = new TreeNode(val);
            q.addLast(node.right);
        }
        return node.val;
    }

    public TreeNode get_root() {
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

3. 二叉树每层最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

分析：

层序遍历的应用：

1. 首先我们需要初始化队列queue、及返回队列ret
2. 当队列不为空时，循环执行出入队
3. 访问每一层前，初始化num为最小值
4. 然后比较获取当前队列中的val最大值，并将最大值加入ret中
5. 根据每个出队的节点，判断该节点的左、右子树是否存在，若存在则执行入队操作
6. 循环3–5步骤，直到队列为空停止，并返回ret即可

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            while (size > 0){
                size--;
                TreeNode node = queue.poll();
                max = Math.max(node.val, max);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            res.add(max);
        }

      return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4. 二叉树底层最左端的树

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

分析：

也是使用层序遍历，只需记录下遍历到最后一层时出队的第一个节点即可。

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        int res = 0;
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            res = queue.peek().val;
            while (size > 0){
                size--;
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5. 二叉树的右侧视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

分析：

层序遍历的应用。记录下遍历每一层时最后一个出队节点即可。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                if (i == len - 1) list.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18