#
##
DFS
BFS
## Stack
[min-stack](https://leetcode-cn.com/problems/min-stack/)
> pushpoptop
```go
type MinStack struct {
min []int
stack []int
}
/** initialize your data structure here. */
func Constructor() MinStack {
return MinStack{
min: make([]int, 0),
stack: make([]int, 0),
}
}
func (this *MinStack) Push(x int) {
min := this.GetMin()
if x < min {
this.min = append(this.min, x)
} else {
this.min = append(this.min, min)
}
this.stack = append(this.stack, x)
}
func (this *MinStack) Pop() {
if len(this.stack) == 0 {
return
}
this.stack = this.stack[:len(this.stack)-1]
this.min = this.min[:len(this.min)-1]
}
func (this *MinStack) Top() int {
if len(this.stack) == 0 {
return 0
}
return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
if len(this.min) == 0 {
return 1 **** > **:** ["2", "1", "+", "3", "*"] > **:** 9
> **:** ((2 + 1) \* 3) = 9
```go
func evalRPN(tokens []string) int {
if len(tokens)==0{
return 0
}
stack:=make([]int,0)
for i:=0;i s = "3[a]2[bc]", "aaabcbc".
> s = "3[a2[c]]", "accaccacc".
> s = "2[abc]3[cd]ef", "abcabccdcdcdef".
```go
func decodeString(s string) string {
if len(s) == 0 {
return ""
}
stack := make([]byte, 0)
for i := 0; i < len(s); i++ {
switch s[i] {
case ']':
temp := make([]byte, 0)
for len(stack) != 0 && stack[len(stack)-1] != '[' {
v := stack[len(stack)-1]
stack = stack[:len(stack)-1]
temp = append(temp, v)
}
// pop '['
stack = stack[:len(stack)-1]
// pop num
idx := 1
for len(stack) >= idx && stack[len(stack)-idx] >= '0' && stack[len(stack)-idx] = 0; j-- {
stack = append(stack, temp[j])
}
}
default:
stack = append(stack, s[i])
}
}
return string(stack)
}
```
DFS
```go
boolean DFS(int root, int target) {
Set visited;
Stack s;
add root to s;
while (s is not empty) {
Node cur = the top element in s;
return true if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in visited) {
add next to s;
add next to visited;
}
}
remove cur from s;
}
return false;
}
```
[binary-tree-inorder-traversal](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)
> **
```go
// stack
func inorderTraversal(root *TreeNode) []int {
result := make([]int, 0)
if root == nil {
return result
}
stack := make([]*TreeNode, 0)
for len(stack) > 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left //
}
//
val := stack[len(stack)-1]
stack = stack[:len(stack)-1]
result = append(result, val.Val)
root = val.Right
}
return result
}
```
[clone-graph](https://leetcode-cn.com/problems/clone-graph/)
>
```go
func cloneGraph(node *Node) *Node {
visited:=make(map[*Node]*Node)
return clone(node,visited)
}
// 1 2
// 4 3
//
func clone(node *Node,visited map[*Node]*Node)*Node{
if node==nil{
return nil
}
//
if v,ok:=visited[node];ok{
return v
}
newNode:=&Node{
Val:node.Val,
Neighbors:make([]*Node,len(node.Neighbors)),
}
visited[node]=newNode
for i:=0;i '1' '0'
```go
func numIslands(grid [][]byte) int {
var count int
for i:=0;i _n_ 1
>
```go
func largestRectangleArea(heights []int) int {
if len(heights) == 0 {
return 0
}
stack := make([]int, 0)
max := 0
for i := 0; i
```go
type MyQueue struct {
stack []int
back []int
}
/** Initialize your data structure here. */
func Constructor() MyQueue {
return MyQueue{
stack: make([]int, 0),
back: make([]int, 0),
}
}
// 1
// 3
// 5
/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int) {
for len(this.back) != 0 {
val := this.back[len(this.back)-1]
this.back = this.back[:len(this.back)-1]
this.stack = append(this.stack, val)
}
this.stack = append(this.stack, x)
}
/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
for len(this.stack) != 0 {
val := this.stack[len(this.stack)-1]
this.stack = this.stack[:len(this.stack)-1]
this.back = append(this.back, val)
}
if len(this.back) == 0 {
return 0
}
val := this.back[len(this.back)-1]
this.back = this.back[:len(this.back)-1]
return val
}
/** Get the front element. */
func (this *MyQueue) Peek() int {
for len(this.stack) != 0 {
val := this.stack[len(this.stack)-1]
this.stack = this.stack[:len(this.stack)-1]
this.back = append(this.back, val)
}
if len(this.back) == 0 {
return 0
}
val := this.back[len(this.back)-1]
return val
}
/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
return len(this.stack) == 0 && len(this.back) == 0
}
/**
* Your MyQueue object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Peek();
* param_4 := obj.Empty();
*/
```
```go
func levelOrder(root *TreeNode) [][]int {
//
result := make([][]int, 0)
if root == nil {
return result
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
list := make([]int, 0)
// length
//
l := len(queue)
for i := 0; i < l; i++ {
//
level := queue[0]
queue = queue[1:]
list = append(list, level.Val)
if level.Left != nil {
queue = append(queue, level.Left)
}
if level.Right != nil {
queue = append(queue, level.Right)
}
}
result = append(result, list)
}
return result
}
```
[01-matrix](https://leetcode-cn.com/problems/01-matrix/)
> 0 1 0
> 1
```go
// BFS 0
// 0 0 0 0
// 0 x 0 0
// x x x 0
// 0 x 0 0
// 0 0 0 0
// 0 1 0 0
// 1 x 1 0
// 0 1 0 0
// 0 0 0 0
// 0 1 0 0
// 1 2 1 0
// 0 1 0 0
func updateMatrix(matrix [][]int) [][]int {
q:=make([][]int,0)
for i:=0;i