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 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 10^4次
代码：
package main import "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. 1 2. / \ 3. 2 3 4. / \ 5. 4 5
返回上下颠倒后的树：
1. 4 2. / \ 3. 5 2 4. / \ 5. 3 1
代码：
package main import "fmt" const null = -1 << 31 type TreeNode struct { Val int Left *TreeNode Right *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, root root.Left, root.Right = nil, nil return newRoot } func levelOrder(root *TreeNode) [][]int { var res [][]int dfs(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 := 1 for 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 } ```
