155. 最小栈 Min Stack

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]输出：
[null,null,null,null,-3,null,0,-2]解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

-2^31 <= val <= 2^31 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 10^4 次

代码：

package mainimport "fmt"type MinStack struct {stack    []int // 数据栈minStack []int // 最小值栈，存储截至当前元素为止的最小值
}func Constructor() MinStack {return MinStack{}
}func (this *MinStack) Push(val int) {this.stack = append(this.stack, val)if len(this.minStack) == 0 || val <= this.minStack[len(this.minStack)-1] {this.minStack = append(this.minStack, val)}
}func (this *MinStack) Pop() {if len(this.stack) == 0 {return}// 若出栈元素是当前最小值，则将最小值栈中对应元素也出栈if this.Top() == this.GetMin() {this.minStack = this.minStack[:len(this.minStack)-1]}this.stack = this.stack[:len(this.stack)-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.minStack) == 0 {return 0}return this.minStack[len(this.minStack)-1]
}func main() {minStack := Constructor()minStack.Push(-2)minStack.Push(0)minStack.Push(-3)n1 := minStack.GetMin()minStack.Pop()n2 := minStack.Top()n3 := minStack.GetMin()fmt.Println(n1, n2, n3)
}

输出：

-3 0 -2

156. 二叉树的上下翻转 Binary Tree Upside Down

给定一个二叉树，满足所有右节点要么是叶子节点，要么没有左兄弟节点，将它上下颠倒并转化为一个树，原来的右节点变成了左叶子节点。返回新的根节点。

例如，给定 binary tree [1,2,3,4,5] 为：

    1/ \2   3/ \
4   5

返回上下颠倒后的树：

   4/ \5   2/ \3   1

代码：

package mainimport "fmt"const null = -1 << 31type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func upsideDownBinaryTree(root *TreeNode) *TreeNode {if root == nil || root.Left == nil && root.Right == nil {return root}newRoot := upsideDownBinaryTree(root.Left)root.Left.Left, root.Left.Right = root.Right, rootroot.Left, root.Right = nil, nilreturn newRoot
}func levelOrder(root *TreeNode) [][]int {var res [][]intdfs(root, 0, &res)return res
}func dfs(node *TreeNode, level int, res *[][]int) {if node == nil {return}if level == len(*res) {*res = append(*res, []int{})}(*res)[level] = append((*res)[level], node.Val)dfs(node.Left, level+1, res)dfs(node.Right, level+1, res)
}func buildTree(nums []int) *TreeNode {if len(nums) == 0 {return nil}root := &TreeNode{Val: nums[0]}Queue := []*TreeNode{root}idx := 1for idx < len(nums) {node := Queue[0]Queue = Queue[1:]if nums[idx] != null {node.Left = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Left)}idx++if idx < len(nums) && nums[idx] != null {node.Right = &TreeNode{Val: nums[idx]}Queue = append(Queue, node.Right)}idx++}return root
}func Array2DToString(array [][]int) string {if len(array) == 0 {return "[]"}arr2str := func(arr []int) string {res := "["for i, ar := range arr {res += fmt.Sprint(ar)if i != len(arr)-1 {res += ","}}return res + "]"}res := "["for i, arr := range array {res += arr2str(arr)if i != len(array)-1 {res += ","}}return res + "]"
}func main() {nums := []int{1, 2, 3, 4, 5}root := buildTree(nums)fmt.Println(Array2DToString(levelOrder(root)))root = upsideDownBinaryTree(root)fmt.Println(Array2DToString(levelOrder(root)))
}

输出：

[[1],[2,3],[4,5]]
[[4],[5,2],[3,1]]

迭代：

```Go
func upsideDownBinaryTree(root *TreeNode) *TreeNode {
   if root == nil {
       return root
   }
   var prev, next, tmp *TreeNode
   for root != nil {
       next = root.Left
       root.Left = tmp
       tmp = root.Right
       root.Right = prev
       prev = root
       root = next
   }
   return prev
}
```