# 剑指offer第三天

### 21.栈的压入、弹出序列

【解题思路】：设计一个辅助栈，如果下一个弹出的数字是辅助栈的栈顶，则弹出，如果不是栈顶，则继续将压入序列压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止；如果所有数字都压入辅助站，栈顶仍然不是欲弹出的数字，则该序列不可能是一个弹出序列。

```import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA == null||popA == null||pushA.length!=popA.length) return false;
Stack<Integer> stack = new Stack<>();
int j = 0;
for(int i = 0 ;i<popA.length;i++){
//一定注意这里需要先判断一下栈是否为空，
//如果为空，则调用peek()时会出现异常;
if(stack.empty())
stack.push(pushA[j++]);
while(stack.peek()!=popA[i]&&j<pushA.length)
stack.push(pushA[j++]);
if(stack.peek()==popA[i])
stack.pop();
else
return false;
}
return true;
}
}```

### 22.从上往下打印二叉树

#### Java知识点：

1. 返回长度：
1. String.length();String字符串用length()方法会返回其长度。
2. Array.length;数组有length属性，直接数组名点length就可以取到。
3. ArrayList.size()方法的会返回其长度。
2. ArrayList 操作： get(),add(),remove() You need to use the get() method to get the element at a particular index from an ArrayList. You can't use [] to get the element at a particular index, in an arraylist. Its possible only for arrays and your files is not an array, but an ArrayList.
```/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
import java.util.ArrayList;
/**

*/
public class Solution {
ArrayList<Integer> result = new ArrayList<>();
ArrayList<TreeNode> temp = new ArrayList<>();
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
if(root == null) return result;
while(temp.size() != 0){
TreeNode node = temp.remove(0);
if(node.left!=null)
if(node.right!=null)
}
return result;
}
}```

### 23.二叉搜索树的后序遍历序列

```public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence == null || sequence.length == 0) return false;
int start = 0,end = sequence.length-1;
return isSearchTree(sequence,start,end);
}
public boolean isSearchTree(int [] sequence,int start,int end){
if(end==start) return true;
int root = sequence[end];
int index = end;
for(int i = start;i<end;i++){
if(sequence[i] > root){
index = i;
break;
}
}
for(int i = index;i<end;i++)
if(sequence[i]< root)
return false;
if(index == end||index == start)// index = end 时没有右子树；index = start时没有左子树；
return isSearchTree(sequence,start,end-1);
else
return isSearchTree(sequence,start,index-1)&&isSearchTree(sequence,index,end-1);
}
}```

### 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 {
private ArrayList<ArrayList<Integer>> allPath = new ArrayList<>();
private ArrayList<Integer> path = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null) return allPath;
target -= root.val;
if(target == 0&& root.left == null&&root.right == null)
else{
FindPath(root.left,target);
FindPath(root.right,target);
}
path.remove(path.size()-1);
return allPath;

}
}```

127 篇文章35 人订阅

0 条评论

## 相关文章

1053

2901

3155

2040

682

2925

3765

25210

### HashMap实现原理分析

HashMap实现原理分析 HashMap主要是用数组来存储数据的，我们都知道它会对key进行哈希运算，哈系运算会有重复的哈希值，对于哈希值的冲突，HashMa...

2905

813