给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList();
int len = nums.length;
if(nums == null || len < 3) return ans;
Arrays.sort(nums); // 排序
for (int i = 0; i < len ; i++) {
if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
int L = i+1;
int R = len-1;
while(L < R){
int sum = nums[i] + nums[L] + nums[R];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
while (L<R && nums[L] == nums[L+1]) L++; // 去重
while (L<R && nums[R] == nums[R-1]) R--; // 去重
L++;
R--;
}
else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return ans;
}
}
2、之字形打印二叉树
题目:请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
#辅助栈
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode ppRootOfTree) {
ArrayList<ArrayList<Integer>> arrayListAllLevel = new ArrayList<>();
if (ppRootOfTree == null) return arrayListAllLevel;
//stack1暂存奇数层结点
Stack<TreeNode> stack1 = new Stack<>();
//stack2暂存偶数层结点
Stack<TreeNode> stack2 = new Stack<>();
//初始层为第一层
int level = 1;
//将第一层的结点按从左到右的顺序入栈
stack1.push(ppRootOfTree);
while (!stack1.isEmpty() || !stack2.isEmpty()){
//保存该层中栈的元素
ArrayList<Integer> arrayListlevel = new ArrayList<>();
//判断是哪一个栈进行出栈操作
if (level % 2 == 1){
//当奇数层执行出栈操作时
//如果stack1还存在元素，则继续出栈
while ( !stack1.isEmpty()){
TreeNode node = stack1.pop();
//在出栈的同时，将此节点的左右子节点入stack2
//同时存入另一个栈的顺序是先存左子节点，再存右子节点
arrayListlevel.add(node.val);
if (node.left != null) stack2.push(node.left);
if (node.right != null) stack2.push(node.right);
}
level ++;
//stack1中所有元素出栈完毕后，将奇数层次的所有元素加入到整个线性表中
arrayListAllLevel.add(arrayListlevel);
}else {
//stack2执行出栈操作
//当偶数层执行出栈操作时
//如果stack2还存在元素，则继续出栈
while ( !stack2.isEmpty()){
TreeNode node = stack2.pop();
//出栈同时加入到奇数层次的数组中
arrayListlevel.add(node.val);
//在出栈的同时，将此节点的左右子节点入stack1
//同时存入另一个栈的顺序是先存右子节点，再存左子节点
if (node.right != null) stack1.push(node.right);
if (node.left != null) stack1.push(node.left);
}
level ++;
//stack2中所有元素出栈完毕后，将偶数层次的所有元素加入到整个线性表中
arrayListAllLevel.add(arrayListlevel);
}
}
return arrayListAllLevel;
}
}
#递归
public static void print(TreeNode root){
if (root == null) {
System.out.println("该树为null");
return;
}
int level = 1;//从根节点第一层遍历
Stack<TreeNode> stackOne = new Stack<>();//用来记录当前遍历的层结点
stackOne.push(root);
printTree(level,stackOne);
}
/**
* 递归遍历整个树
* @param level 当前树的层次
* @param from 当前层的所有结点信息
*/
public static void printTree(int level,Stack<TreeNode> from){
if (from == null || from.empty()) {
return;
}
//用来存储下一层所有结点的信息
Stack<TreeNode> to = new Stack<>();
System.out.print(level+" : ");
//当前层次为奇数，从左向右遍历
if (level %2 != 0) {
while(!from.empty()){
TreeNode node = from.pop();
if (node != null) {
System.out.print(node.val+"\t");
if (node.left != null) {
to.push(node.left);
}
if (node.right != null) {
to.push(node.right);
}
}
}
}else{
//当前为偶数层，需要从右向左遍历
while(!from.empty()){
TreeNode node = from.pop();
//当前节点不为null，或者不是叶子结点
if (node != null) {
System.out.print(node.val+"\t");
if (node.right != null) {
to.push(node.right);
}
if (node.left != null) {
to.push(node.left);
}
}
}
}
System.out.println();
//递归
printTree(++level,to);
}
#非递归
public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
if (pRoot == null) {
return null;
}
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
//二叉树的层次标记
int level = 1;
//保存二叉树当前层次的结点信息
Stack<TreeNode> concurrent = new Stack<>();
concurrent.push(pRoot);
while (!concurrent.isEmpty()){
Stack<TreeNode> to = new Stack<>();
ArrayList<Integer> list = new ArrayList<>();
if (level%2==0){
while (!concurrent.isEmpty()){
TreeNode node = concurrent.pop();
if (node != null) {
//将当前的val添加到list中
list.add(node.val);
//输出当前结点val
System.out.print(node.val+" ");
//偶数层从有向左记录下层结点
if (node.right != null) {
to.push(node.right);
}
if (node.left != null) {
to.push(node.left);
}
}
}
}else {
while (!concurrent.isEmpty()){
TreeNode node = concurrent.pop();
if (node != null) {
//将当前的val添加到list中
list.add(node.val);
//输出当前结点val
System.out.print(node.val+" ");
//奇数层从左向右记录下一层所有结点
if (node.left != null) {
to.push(node.left);
}
if (node.right != null) {
to.push(node.right);
}
}
}
}
//将一层信息添加到结果列表
result.add(list);
//当前层转向下一层
concurrent = to;
//层级标记增加
level++;
//输出结果换行显示
System.out.println();
}
return result;
}
京公网安备 11010502036488号