5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路及方法
这道题使用中心扩展算法，先写一个函数，用双指针的方法从中心扩展找到回文串。然后调用该方法，从字符串的开头寻找回文串，并对比长度。
注意，因为回文串的长度有奇有偶，所以用中心算法的时候，奇数就以单个字符为中心，偶数就用两个字符为中心。
class Solution {
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
// 寻找以s[i]为中心的奇数长度回文串
String s1 = findPalindrome(s, i, i);
// 寻找以s[i]、s[i + 1]为中心的偶数长度回文串
String s2 = findPalindrome(s, i, i + 1);
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
public String findPalindrome(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
// 向两边扩张
left--;
right++;
}
return s.substring(left + 1, right);
}
}
结果如下：
剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路及方法
很简单的层次遍历算法，只不过题目要求的是Z字型，所以我们用层数来区分。当层数为偶数层的时候将当前出队序列翻转即可。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int step = 1;
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> row = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
row.add(cur.val);
// 子结点入队
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
}
if (step % 2 == 0) Collections.reverse(row);
res.add(row);
step++;
}
return res;
}
}
结果如下：
