21.栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA==null || popA==null){
return false;
}else if(pushA.length==0 ||popA.length==0){
return false;
}
ArrayList<Integer> list =new ArrayList<Integer>();
int push = pushA[0];
int pop = popA[0];
int i=0,j=0;
while(true){
if(push==pop){
//优先从队列中取出一个
if(list.size()!=0){
push=list.remove(list.size()-1);
}else{
i++;//如果队列里面没有，就从后面拿一个
if(i==pushA.length){
i=i-1;
break;
}
push=pushA[i];
}
j++;
if(j==popA.length){
break;
}
pop=popA[j];
}else{
list.add(push);
i++;
if(i==pushA.length){
break;
}
push=pushA[i];
}
}
if(j==popA.length-1&&i==pushA.length-1){
if(list.size()==0){
return true;
}else{
return false;
}
}
return false;
}
}
22.从上往下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
import java.util.ArrayList;
/**
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<TreeNode> list = new ArrayList<TreeNode>();
ArrayList<Integer> res = new ArrayList<Integer>();
if(root!=null){
list.add(root);
}
while(!list.isEmpty()){
TreeNode tmp = list.remove(0);
TreeNode left =tmp.left;
TreeNode right = tmp.right;
res.add(tmp.val);
if(left!=null){
list.add(left);
}
if(right!=null){
list.add(right);
}
}
return res;
}
}
23.二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null || sequence.length==0){
return false;
}
return check(sequence,0,sequence.length-1);
}
public boolean check(int[] array,int start,int end){
if(start>=end){
return true;
}
int size = end -start ;//最后一个不要跟自己比，去掉最后一个
int endVal =array[end];
//找出第一个比endVal大的位置
int mark=-1;
for(int i =start;i< size;i++){
if(array[i]>endVal){
mark=i;
break;
}
}
if(mark==-1){//都比endVal小
if(check(array,start,end-1)){
return true;
}
}else{
//mark之后的数都要比val大
for(int i=mark;i<size;i++){
if(array[i]<endVal){
return false;
}
}
if(check(array,start,mark-1) && check(array,mark,end-1)){
return true;
}
}
return false;
}
}
24.二叉树中和为某一值的路径
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<ArrayList<Integer>> res =travel(new ArrayList<Integer>(),target,root);
return res;
}
public ArrayList<ArrayList<Integer>> travel(ArrayList<Integer> list,int value,TreeNode root){
//为空的情况
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
if(root==null){
return res;
}
ArrayList<Integer> newList =new ArrayList<Integer>();
//将list中的内容复制到newlist中
for(Integer item:list){
newList.add(item);
}
int val = root.val;
newList.add(val);
int rest = value-val;
//叶子节点
if(root.left==null && root.right==null){
if(rest==0){
res.add(newList);
}else{
return res;
}
}else{//不是叶子节点
ArrayList<ArrayList<Integer>> left = travel(newList,rest,root.left);
ArrayList<ArrayList<Integer>> right = travel(newList,rest,root.right);
//合并两项，并返回
if(left!=null){
for(ArrayList<Integer> item:left){
res.add(item);
}
}
if(right!=null){
for(ArrayList<Integer> item:right){
res.add(item);
}
}
}
return res;
}
}
25.复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。
import java.util.ArrayList;
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
//如果为空
if(pHead==null){
return null;
}
//存储地址
ArrayList<String> addresses=new ArrayList<String>();
addresses.add(pHead.toString());
//记录头指针
RandomListNode first = pHead;
//记录头指针
RandomListNode newOne = new RandomListNode(pHead.label);
//存储指针
ArrayList<RandomListNode> res = new ArrayList<RandomListNode>();
res.add(newOne);
RandomListNode entity =newOne;
//int size=1;
while(pHead.next!=null){
pHead=pHead.next;
//获取当前地址
String address =pHead.toString();
//if(addresses.contains(address)){//已经存在,回路
// entity.next = res.get(addresses.indexOf(address));//获取
// break;
//}
//size++;
entity.next = new RandomListNode(pHead.label);
entity = entity.next;
res.add(entity);
addresses.add(pHead.toString());//默认是地址
}
pHead = first;
if(pHead.random!=null){
newOne.random = res.get(addresses.indexOf(pHead.random.toString()));
}
entity=newOne;
//int i=0;
while(pHead.next!=null /*&& i<size*/){
pHead=pHead.next;
entity=entity.next;
if(pHead.random!=null){
entity.random = res.get(addresses.indexOf(pHead.random.toString()));
}
//i++;
}
return newOne;
}
}
