- 1.二维数组中的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：比较矩阵的右上角的数与target的大小，如果target比这个矩阵右上角的数大，由于矩阵的右上角的元素值是其所在行的最大的值，所以target肯定不在其所在的行了，所以这时候就应该在其下一行中去找这个target;
如果target比矩阵右上角的数A小，那么由于A所在的列中A是最小的，那么target就在其左边的列中。
如果相等，返回true;
public class Solution {
public boolean Find(int target, int [][] array) {
int row = 0;
int col = array[0].length - 1;
while(row < array.length && col >= 0){
if(array[row][col] == target){
return true;
}else if(target > array[row][col]){
row++;
}else{
col--;
}
}
return false;
}
}
- 2.替换空格
题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：两种方式
① 如果允许使用StringBuffer自带的函数如append()，则非常容易解决。见代码函数replaceSpace1()。
②如果不允许使用StringBuffer自带的函数，则理解为一个空格变成了%20，也就是说每有一个空格，长度要增加2，所以首先先计算有多少个空格，这样长度就能增加多少，得到增加后的长度newStrLength。之后创建一个长度为newStrLength的字符数组，从尾到头开始复制原来的数组，在复制的过程中，如果字符不是空格，直接复制，如果字符是空格，那么需要把这个空格变成%20（这个复制过程就是把新建的数组比如现在到了 K这个位置，然后就是K，K-1，K-2这三个位置依次变成0,2，%这三个字符，因为是从后往前复制的所以是倒序），重复这个过程就行。
public String replaceSpace(StringBuffer str) {
if(str == null){
return null;
}
StringBuffer result = new StringBuffer();
for(int i = 0; i < str.length(); i++){
if(str.charAt(i) == ' '){
result.append("%");
result.append("2");
result.append("0");
}else{
result.append(str.charAt(i));
}
}
return result.toString();
}
public String replaceSpace2(StringBuffer str) {
String str1 = str.toString();
if(str1.equals("")){
return str1;
}
int SpaceLength = 0;
char[] charArray = str1.toCharArray();
for(int i = 0; i < charArray.length;i++){
if(charArray[i] == ' '){
SpaceLength++;
}
}
int newStrLength = charArray.length + SpaceLength*2;
char[] resultCharArray = new char[newStrLength];
int j = resultCharArray.length - 1;
int i = charArray.length - 1;
while(i >= 0){
if(charArray[i] != ' '){
resultCharArray[j--] = charArray[i--];
}else{
resultCharArray[j--] = '0';
resultCharArray[j--] = '2';
resultCharArray[j--] = '%';
i--;
}
}
return new String(resultCharArray);
}
- 3.从尾到头打印链表
题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
思路：
①剑指offer的思路，递归的思路，只要链表不为空，一直往后进行遍历，然后直到到达链表的末尾，就开始用数组保存下来结果。
②如果栈可用的情况下，先将链表值逐一入栈，再将栈内值逐一弹出至ArrayList中。
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> result = new ArrayList<>();
if(listNode == null){
return result;
}
printListFromTailToHead(listNode,result);
return result;
}
public void printListFromTailToHead(ListNode listNode,ArrayList<Integer> list){
if(listNode.next != null){
printListFromTailToHead(listNode.next,list);
}
list.add(listNode.val);
}
public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while(listNode != null){
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> result = new ArrayList<>();
while(!stack.isEmpty()){
result.add(stack.pop());
}
return result;
}
}
- 4.用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：针对队列的push方法，使用栈的push()方法即可，对于队列的pop方法，则需要将栈1的元素先逐一丢到栈二中，并把栈二的顶部元素返回，再丢回栈一中，以满足先入先出的顺序。
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
int result = stack2.pop();
while(!stack2.isEmpty()){
stack1.push(stack2.pop());
}
return result;
}
}
- 5.旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：根据题意说明是一个递增数组的旋转，所以如题所示【3,4,5】，【1,2】还是局部递增的，使用二分的方式解答：
1.先取出array[mid]，和array[end]比较，如果array[mid]>array[end]，则说明mid之前的某些部分旋转到了后面，所以下次寻找 start = mid+1 开始。
2.取出的array[mid]<array[end]，则说明从array[mid]到array[end]之间都应为被旋转的部分，所以最小应该在mid的前面，但是也有可能当前的mid 就是最小的值 所以下次所需找的元素所在区间必然是【start,mid】故令end = mid。
3.当array[mid] = array[end]的时候，说明数组中存在着相等的数值，可能是这样的形式 【2,2,2,2,1,2】所以 选择start加1作为下次寻找的上界。
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0){
return 0;
}
if(array[array.length-1] > array[0]){
return array[0];
}
int start = 0;
int end = array.length - 1;
while(start != end){
int mid = (start + end) / 2;
if(array[mid] > array[end]){
start = mid + 1;
}else if(array[mid] < array[end]){
end = mid;
}else{
start++;
}
}
return array[end];
}
}
- 6.斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。(n<=39)
思路：①递归（测试用例中肯定有一个栈深度极深，然后溢出）
②剑指offer思路，每次使用两个变量a,b来计算下一个数的值sum,然后a,b,sum分别是斐波那契数列中的三个数，那么就令a=b,b=sum,这样a和b就往下移动了一个位置，再计算sum就是第4个数了，重复这个过程即可。
public class Solution {
//递归方法
public int Fibonacci(int n) {
if(n == 0){
return 0;
}else if(n <= 1){
return 1;
}
return Fibonacci(n-1)+Fibonacci(n-2);
}
//非递归方法
public int Fibonacci2(int n) {
int first = 0;
int second = 1;
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
int sum = 0;
for(int i = 2; i <= n; i++){
sum = first+second;
first = second;
second = sum;
}
return sum;
}
}
- 7.跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路：①递归
② 每次使用两个变量a,b来计算下一个数的值sum,然后a,b,sum分别是斐波那契数列中的三个数，那么就令a=b,b=sum,这样a和b就往下移动了一个位置，再计算sum就是第4个数了，重复这个过程即可。
public class Solution {
//递归方法
public int JumpFloor(int target) {
if(target == 0){
return 0;
}
if (target == 1) {
return 1;
}
if (target == 2){
return 2;
}
return JumpFloor(target-1)+JumpFloor(target-2);
}
//非递归方法
public int JumpFloor(int target) {
if (target == 1) {
return 1;
}
if (target == 2){
return 2;
}
int first = 1;
int second = 2;
int sum = 0;
for(int i = 3; i <= target; i++){
sum = first + second;
first = second;
second = sum;
}
return sum;
}
}
- 8.变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路： ①动态规划法
② 因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
所以f(n)=2*f(n-1)
public class Solution {
//动态规划
public int JumpFloorII(int target) {
if(target == 0) {
return 0;
}
int[] dp = new int[target+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= target; i++){
dp[i] = 0;
for(int j = 0; j < i; j++){
dp[i] += dp[j];
}
}
return dp[target];
}
}
//数学归纳法
public int JumpFloorII(int target) {
if(target == 0){
return 0;
}
if(target == 1){
return 1;
}
return 2 * JumpFloorII(target - 1);
}
}
- 9.矩形覆盖
题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路： ①递归
②每次使用两个变量a,b来计算下一个数的值sum,然后a,b,sum分别是数列中的三个数，那么就令a=b,b=sum,这样a和b就往下移动了一个位置，再计算sum就是第4个数了，重复这个过程即可。
public class Solution {
public int RectCover(int target) {
if(target == 0){
return 0;
}
if(target == 1){
return 1;
}
if(target == 2){
return 2;
}
int first = 1;
int second = 2;
int sum = 0;
for(int i = 3; i <= target; i++){
sum = first+second;
first = second;
second = sum;
}
return sum;
}
}
- 10.二进制中1的个数
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路：思路
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n != 0){
n = n & (n-1);
count++;
}
return count;
}
}
- 11.链表中倒数第k个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路：快慢指针，快指针先走k-1步，然后快慢指针一起走，当快指针走到末尾，那么慢指针就到了倒数第K个节点了。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null){
return null;
}
int length = 0;
ListNode temp = head;
while(temp != null){
length++;
temp = temp.next;
}
if(length < k){
return null;
}
ListNode fast_p = head;
ListNode slow_p = head;
for(int i = 0; i < k; i++){
fast_p = fast_p.next;
}
while(fast_p != null){
slow_p = slow_p.next;
fast_p = fast_p.next;
}
return slow_p;
}
}
- 12.翻转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
思路：快慢指针，快指针先走k-1步，然后快慢指针一起走，当快指针走到末尾，那么慢指针就到了倒数第K个节点了。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null){
return head;
}
ListNode newH = null;
ListNode p = head;
while(p != null){
ListNode temp = p.next;
p.next = newH;
newH = p;
p = temp;
}
return newH;
}
}
- 12.合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路：归并排序
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
curr.next = list1;
curr = curr.next;
list1 = list1.next;
}else{
curr.next = list2;
curr = curr.next;
list2 = list2.next;
}
}
if(list1 != null){
curr.next = list1;
}
if(list2 != null){
curr.next = list2;
}
return dummy.next;
}
}
- 13.数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
思路：穷举
public class Solution {
public double Power(double base, int exponent) {
if(exponent == 0){ //指数是0
if(equalZero(base) == true){
return 0; //如果底数是0则返回0
}
return 1;//除了0的任何数的0次方是1
}
if(exponent > 0){
return complex(base,exponent);//直接计算base的exponent次方返回即可
}
if(equalZero(base)){
if(base > 0){
return Double.POSITIVE_INFINITY; //底数是正0
}
if(exponent % 2 == 0){//指数是偶数次方
return Double.POSITIVE_INFINITY;//返回正无穷
}
return Double.NEGATIVE_INFINITY;
}
return 1/complex(base,exponent);
}
double complex(double base,int exponent){
double result = 1.0;
if(exponent < 0)//如果指数小于0，比如2的-3次方，先计算2的3次方，然后求倒数
exponent = 0 - exponent;
for(int i = 0; i < exponent; i++)
result = result * base;
return result;
}
boolean equalZero(double base){
//判断一个doule类型的数是不是0，必须这样判断，不能直接与0进行比较，因为浮点数本身不精确
if(base >0 && base < 0.00000001)
return true;
if(base < 0 && base > -0.00000001)
return true;
return false;
}
}
- 14.调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路：题目明确说了，不能修改相对位置，所以只能是用以下的新建两个数组，一个奇数数组，一个偶数数组，然后把奇数和偶数分别保存到对应的数组，然后在赋值到原数组中.
import java.util.ArrayList;
public class Solution {
public void reOrderArray(int [] array) {
ArrayList<Integer> odd = new ArrayList<>();
ArrayList<Integer> even = new ArrayList<>();
for(int i = 0; i < array.length; i++){
if(array[i] % 2 == 1){
odd.add(array[i]);
}else{
even.add(array[i]);
}
}
for(int i = 0; i< odd.size();i++){
array[i] = odd.get(i);
}
for(int i = 0; i< even.size();i++){
array[odd.size()+i] = even.get(i);
}
}
}
- 15.数组中出现次数超过一半的数
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路：使用一个计数count = 1，并以number=array[0],每当数组中数和当前数number相同，那么count就加1，不相同就减1，因为是找出现的数超过数组的长度的一半，所以最后如果有出现的数超过数组长度一半的，count肯定是大于0的数。但是有一种特殊情况，即最后连续出现两次该数，也可能导致count > 0，因此需要再次遍历链表确定是否大于链表长度的1/2。
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length == 0){
return 0;
}
int count = 1;
int number = array[0];
for(int i = 1; i < array.length; i++){
if(array[i] == number){
count++;
}else{
count--;
if(count == 0){
number = array[i];
count = 1;
}
}
}
if(count > 0){
count = 0;
for(int i = 0; i < array.length; i++){
if(number == array[i]){
count++;
}
}
if(count > array.length/2){
return number;
}
}
return 0;
}
}
- 16.二叉树的镜像
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
思路：使用临时变量保存左子树（否则会被修改）。递归处理左右子树。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root != null){
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
if(root.left != null){
Mirror(root.left);
}
if(root.right != null){
Mirror(root.right);
}
}
}
}
- 17.第一个只出现一次的字符
题目描述
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
思路：字符串中的字符都是英文的字母，所以每一个字母都有一个ASCII码与其对应，然后建立一个字符数组长度是256，可以把每一个字符对应一个数组的下标
然后设立一个index！然后比如字符a第一次出现那么strArray[a字符对应的ASC码] = index;然后如果下一次a再出现了，那么strArray[a字符对应的ASC码] = -1；这样子做，只要字符出现了大于等于2次，都会这样子等于-1
而只出现一次的字符，由于index这个变量是每次递增的！我们只需要遍历一遍，找index最小的那个字符。
public class Solution {
public int FirstNotRepeatingChar(String str) {
if(str.equals("")){
return -1;
}
int[] temp = new int[256];
int index = 1;
char[] charArray = str.toCharArray();
for(int i = 0; i < charArray.length; i++){
if(temp[(int)charArray[i]] == 0){
temp[(int)charArray[i]] = index;
index++;
}else{
temp[(int)charArray[i]] = -1;
}
}
int minIndex = Integer.MAX_VALUE;
char ch = '1';
for(int i=0; i < temp.length; i++){
if(temp[i] > 0)
{
if(temp[i] < minIndex)
{//找最小的index对应的字符
minIndex = temp[i];
ch = (char)i;
}
}
}
int result = -1;
for(int i=0;i<charArray.length;i++)
{//去找这个字符的下标！
if(charArray[i] == ch)
return i;
}
return -1;
}
}
- 18.二叉树的深度
题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
思路：递归
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private int max_depth;
public int TreeDepth(TreeNode root) {
if(root == null){
return 0;
}
int left_depth = TreeDepth(root.left);
int right_depth = TreeDepth(root.right);
int max_depth = Math.max(left_depth,right_depth)+1;
return max_depth;
}
}
- 19.平衡二叉树
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
思路：递归
/**
public class Solution {
private boolean result = true;
public boolean IsBalanced_Solution(TreeNode root) {
maxDepth(root);
return result;
}
public int maxDepth(TreeNode root){
if(root == null){
return 0;
}
int left_depth = maxDepth(root.left);
int right_depth = maxDepth(root.right);
if ((Math.abs(left_depth-right_depth))>1){
result = false;
}
return Math.max(left_depth,right_depth)+1;
}
}
- 20.对称二叉树
题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路：递归
/**
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot){
return isMirror(pRoot,pRoot);
}
boolean isMirror(TreeNode t1,TreeNode t2){
if(t1 == null && t2 == null){
return true;
}
if(t1 == null || t2 == null){
return false;
}
return ((t1.val == t2.val)&& isMirror(t1.left,t2.right) && isMirror(t1.right,t2.left));
}
}
``
- **21.不用加减乘除做加法**
>**题目描述**
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
>**思路**：先想之前的十进制怎么加减，以5+8为例子，先进行按位计算，得到3，再考虑进位，得到10。之后再将10和3按位相加得到结果13。二进制也可以类似这样的方法，举个例子 4+5（即二进制100 + 101）先让其按位进行异或运算，得到001先保存，在让两者进行按位与运算，得100，为其进位为，在将其左移一位，得1000。再令1000和001进行抑或运算得1001，再进行按位与运算，得0，跳出循环，则结果就是1001。
/**
/*
public class Solution {
public int Add(int num1,int num2) {
int sum = 0;
int carry = 0;
do{
sum = num1 ^ num2;
carry = num1 & num2;
if(carry != 0){
carry = carry << 1;
}
num1 = sum;
num2 = carry;
}while(carry != 0);
return sum;
}
}
- **22.求1+2+3+...+n**
>**题目描述**
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
>**思路**：使用&&运算中的短路思想，递归的解决问题。
public class Solution {
private int result = 0;
public int Sum_Solution(int n) {
complex(n);
return result;
}
public int complex(int n){
boolean flag = (n-1) >= 0 && (result = result + n) > 0 && complex(n-1) > 0;
return result;
}
}
- **23.包含min函数的栈**
>**题目描述**
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
>**思路**：使用一个辅助栈去维护最小值。
import java.util.Stack;
//时间复杂度O(1)
public class Solution {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public void push(int node) {
stack1.push(node);
if(stack2.isEmpty()){
stack2.push(node);
}else{
if(node <= (int)stack2.peek()){
stack2.push(node);
}else{
stack2.push(stack2.peek());
}
}
}
public void pop() {
stack1.pop();
stack2.pop();
}
public int top() {
return (int)stack1.peek();
}
public int min() {
return (int)stack2.peek();
}
}
- **24.栈的压入、弹出序列**
>**题目描述**
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
>**思路**：使用一个辅助栈，先按压入序列将第一个元素压入，之后开始比较弹出序列与该栈栈顶是否相同，不同则继续按压入顺序入栈，直到栈顶元素和弹出数列相等是出栈，如果入栈已超过压入顺序，且栈顶仍不与弹出数列的值相等，则不是对应的序列。
import java.util.ArrayList;
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length != popA.length){
return false;
}
Stack<Integer> stack = new Stack<>();
stack.push(pushA[0]);
int j = 1;
for(int i = 0; i < popA.length; i++){
while(j < pushA.length && (int)stack.peek() != popA[i]){
stack.push(pushA[j]);
j++;
}
if(j >= pushA.length && stack.peek()!=popA[i]){
return false;
}else{
stack.pop();
}
}
return true;
}
}
- **25.从上往下打印二叉树**
>**题目描述**
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
>**思路**：使用一个队列进行层序遍历。
import java.util.ArrayList;
import java.util.;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null){
return result;
}
queue.offer(root);
while(!queue.isEmpty()){
TreeNode treeNode = queue.poll();
if (treeNode.left != null) {
queue.offer(treeNode.left);
}
if (treeNode.right != null) {
queue.offer(treeNode.right);
}
result.add(treeNode.val);
}
return result;
}
}
