Leetcode Practice

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right{
        mid := （right - left) >> 1 + left
        if nums[mid] == target{
            return mid
        }else if nums[mid] < target {
            left = mid + 1
        }else{
            right = mid - 1
        }
    }
   return -1
}

func solution(nums []int) int {
    if len(nums) < 3 {
        return -1
    }
    left, right := 0, len(nums)-1
    for left+3 < right {
        mid := left + (right-left)>>1
        if mid%2 == 1 {
            if nums[mid] == nums[mid+1] {
                right = mid - 1
            } else if nums[mid] == nums[mid-1] {
                left = mid + 1
            } else {
                return nums[mid]
            }
        } else {
            if nums[mid] == nums[mid-1] {
                right = mid - 2
            } else if nums[mid] == nums[mid+1] {
                left = mid + 2
            } else {
                return nums[mid]
            }
        }
    }

    if left == 0 {
        return nums[left]
    }
    if right == len(nums)-1 {
        return nums[right]
    }

    return -1
}

func searchRange(nums []int, target int) []int {
    res := []int{-1, -1}
    if len(nums) == 0{
        return res
    }
    left, right := 0, len(nums) - 1
    for left <= right{
        mid := left + (right-left)>>1
        if nums[mid] >= target{
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    // 5 7 7      8    8 10
    //     right  left
    if left <= len(nums) - 1 && nums[left] == target{
        res[0] = left
    }

    left, right = 0, len(nums) - 1
    for left <= right{
        mid := left + (right-left)>>1
        if nums[mid] <= target{
            left = mid + 1
        }else {
            right = mid - 1
        }
    }
    // 5 7 7 8 8      10
    //         right  left
    if right >= 0 && nums[right] == target{
        res[1] = right
    }

    return res
}

// 方法一
func removeElement(nums []int, val int) int {
    left, right := 0, len(nums) - 1
    for left <= right{
        if nums[left] == val {
            if nums[right] != val{
                nums[left], nums[right] = nums[right], nums[left]
                left++
                right--
            }else{
                right--
            }
        }else{
             if nums[right] != val{
               left ++
            }else{
                right--
                left ++
            }
        }
    }

    return right+1
}

// 方法二
// 快慢指针
// 新数组比旧数组短，从左填充
// String部分的Replace Space，新数组比旧数组长，从右填充
func removeElement(nums []int, val int) int {
    left := 0
    for _, v := range nums{
        if v != val{
            nums[left] = v
            left++
        }
    }

    return left
}

// 方法一
func sortedSquares(nums []int) []int {
    res := make([]int, len(nums))
    left, right, k := 0, len(nums)-1, len(nums)-1
	for ; left <= right; k-- {
        if nums[left] * nums[left] > nums[right] * nums[right]{
            res[k] = nums[left] * nums[left]
            left++
        }else{
            res[k] = nums[right] * nums[right]
            right--
        }
    }
    return res
}

// 方法二
func sortedSquares(nums []int) []int {
    for i, value := range nums {
        nums[i] = value * value
    }
    sort.Ints(nums)
    return nums
}

func minSubArrayLen(target int, nums []int) int {
    left, sum, res := 0, 0, len(nums) + 1
    for right, v := range nums{
        sum += v
        for sum >= target{
            res =  min(res, right - left + 1)
            sum -= nums[left]
            left ++
        }
    }

    if res == len(nums) + 1{
        res = 0
    }

    return res
}

func min(a, b int)int{
    if a <= b{
        return a
    }
    return b
}

func generateMatrix(n int) [][]int {
    top, bottom := 0, n-1
    left, right := 0, n-1
    num := 1
    tar := n * n
    matrix := make([][]int, n)
    for i := 0; i < n; i++ {
        matrix[i] = make([]int, n)
    }
    for num <= tar {
        for i := left; i <= right; i++ {
            matrix[top][i] = num
            num++
        }
        top++
        for i := top; i <= bottom; i++ {
            matrix[i][right] = num
            num++
        }
        right--
        for i := right; i >= left; i-- {
            matrix[bottom][i] = num
            num++
        }
        bottom--
        for i := bottom; i >= top; i-- {
            matrix[i][left] = num
            num++
        }
        left++
    }
    return matrix
}

func lengthOfLongestSubstring(s string) int {
    m := make(map[rune]int)
    left, res := 0, 0
    for right, v := range s{
        if v2, ok := m[v]; ok && left <= v2{
            left = v2 + 1
        }

        m[v] = right

        if v3 := right - left + 1; v3 > res{
            res = v3
        }
    }
    return res
}

// 方法一
func searchInsert(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    for left <= right {
        mid := left + (right - left) / 2 // 防求和溢出
        if nums[mid] == target {
            return mid
        }else if nums[mid] > target{
            right = mid - 1
        }else{
            left = mid + 1
        }
    }

	 // 此时 right + 1 == left
    // nums[right] < target < nums[left]

    return left
}

// 方法二
// nums[right] is the biggest number less than the target
func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)>>1
        if nums[mid] >= target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return right+1
}

func moveZeroes(nums []int)  {
    if len(nums) == 0{
        return
    }

    left := 0
    for right, v := range nums{
        if v != 0{
            nums[right] = 0
            nums[left] = v
            left++
        }
    }
}

func moveZeroes(nums []int) {
	// j stay on the index of zero
    j := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] != 0 {
            if i != j {
                nums[i], nums[j] = nums[j], nums[i]
                j++
            } else {
                j++
            }
        }
    }
}

import (
	"sort"
)

func numRescueBoats(people []int, limit int) int {
    sort.Ints(people)
    left, right, res := 0, len(people)-1, 0
    for left <= right {
        if left == right {
            res++
            return res
        }
        if people[left]+people[right] <= limit {
            left++
            right--
        } else {
            right--
        }
        res++
    }
    return res
}

type NumMatrix struct {
    preSum [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    m := len(matrix)
    n := len(matrix[0])

    preSum := make([][]int, m+1)
    for i := 0; i < m+1; i++{
        preSum[i] = make([]int, n+1)
    }

    for i := 0; i < m; i++{
        for j := 0; j < n; j++{
            // matrix[i][j] = preSum[i+1][j+1] - (preSum[i][j+1] - preSum[i+1][j] + preSum[i][j])
            preSum[i+1][j+1] = preSum[i][j+1] + preSum[i+1][j] - preSum[i][j] + matrix[i][j]
        }
    }
    return NumMatrix{preSum:preSum}

}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    preSum := this.preSum
    return preSum[row2+1][col2+1] - preSum[row2+1][col1] - preSum[row1][col2+1] + preSum[row1][col1]
}

func removeElements(head *ListNode, val int) *ListNode {
    preHead := new(ListNode)
    preHead.Next = head
    pre := preHead
    cur := head
    for cur != nil{
        if cur.Val == val{
            pre.Next = cur.Next
            cur = cur.Next
        }else{
            pre = cur
            cur = cur.Next
        }
    }
    return preHead.Next
}

// cur.Next=nil, 倒数第1个节点
// cur.Next.Next=nil, 倒数第2个节点
// 按规律找出倒数第n+1个节点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	preHead := new(ListNode)
	preHead.Next = head
	left := preHead
	right := preHead
	for i := 0; i < n+1; i++{
		right = right.Next
	}
	for right != nil{
		right = right.Next
		left = left.Next
	}
	left.Next = left.Next.Next
	return preHead.Next
}

func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    for cur != nil{
        cur.Next, pre, cur = pre, cur, cur.Next
    }
    return pre
}

// 递归
func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil{
        return head
    }

    newHead := head.Next
    head.Next.Next, head.Next =  head, swapPairs(head.Next.Next)

    return newHead
}

// 迭代
func swapPairs(head *ListNode) *ListNode {
    preHead := new(ListNode)
    preHead.Next = head
    cur := preHead
    for cur.Next != nil && cur.Next.Next != nil{
        cur.Next,
        cur.Next.Next.Next,
        cur.Next.Next,
        cur =
        cur.Next.Next,
        cur.Next,
        cur.Next.Next.Next,
        cur.Next

        // cur, cur.Next, cur.Next.Next, cur.Next.Next.Next =
        // cur.Next, cur.Next.Next, cur.Next.Next.Next, cur.Next
    }
    return preHead.Next
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    curA, curB := headA, headB
    lengtA, lengtB := 0, 0
    for curA != nil{
        lengtA++
        curA = curA.Next
    }
    for curB != nil{
        lengtB++
        curB = curB.Next
    }
    curA, curB = headA, headB
    if lengtA < lengtB{
        lengtA, lengtB = lengtB, lengtA
        curA, curB = curB, curA
    }

    for i := 0; i < lengtA-lengtB; i++{
        curA = curA.Next
    }

    for i := 0; i < lengtB; i++{
        if curA == curB{
            return curA
        }
        curA = curA.Next
        curB = curB.Next
    }

    return nil
}

func detectCycle(head *ListNode) *ListNode {
    if head == nil|| head.Next == nil{
        return nil
    }

    intersection := findIntersection(head)
    // no circle
    if intersection == nil{
        return nil
    }

    fast := head
    slow := intersection
    for fast != slow {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}

func findIntersection(head *ListNode) *ListNode{
    fast, slow := head, head
    for slow != nil && fast != nil && fast.Next != nil{
        fast = fast.Next.Next
        slow = slow.Next
        if slow == fast{
            return slow
        }
    }
    return nil
}

func isAnagram(s string, t string) bool {
    m := make(map[rune]int)
    for _, v := range s{
        m[v] ++
    }

    for _, v := range t{
        m[v] --
    }

    for _, v := range m{
        if v != 0{
            return false
        }
    }
    return true
}

func canConstruct(ransomNote string, magazine string) bool {
    m := make(map[rune]int)
    for _, v := range ransomNote{
        m[v]++
    }

    for _, v := range magazine{
        if _, ok := m[v]; ok{
            m[v]--
        }
    }

    for _, v := range m{
        if v > 0{
            return false
        }
    }

    return true
}

func intersection(nums1 []int, nums2 []int) []int {
    m := make(map[int]bool)
    var res []int
    for _, n := range nums1 {
        m[n] = true
    }
    for _, n := range nums2 {
            if m[n] {
                //delete(m, n)
                m[n] = false
                res = append(res, n)
            }
    }
    return res
}

func isHappy(n int) bool {
    m := make(map[int]bool)
    for n != 1{
        if m[n]{
            return false
        }
        m[n] = true
        n = calcu(n)
    }
    return true
}

func calcu(n int)int{
    sum := 0
    for n != 0{
        rem := n % 10
        sum = sum + rem*rem
        n = n / 10
    }
    return sum
}

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for k, v := range nums{
        if v2, ok := m[target-v]; ok{
            return []int{v2, k}
        }else{
            m[v] = k
        }
    }
    return nil
}

import "sort"

func threeSum(nums []int) [][]int {
    res := make([][]int, 0)
    sort.Ints(nums)
    length := len(nums)
    for i := 0; i < length; i++{
        // De-duplication
        // same with last element
        if i > 0 && nums[i] == nums[i-1]{
            continue
        }
        left, right := i+1, length-1
        for left < right{
            sum := nums[i] + nums[left] + nums[right]
            if sum < 0{
                left++
            }else if sum > 0{
                right--
            }else{
                res = append(res, []int{nums[i], nums[left], nums[right]})
                for left < right && nums[right] == nums[right-1]{
                    right--
                }
                for left < right && nums[left] == nums[left+1]{
                    left++
                }
                right--
                left++
            }
        }
    }
    return res
}


func threeSum(nums []int) [][]int {
    res := make([][]int, 0)
    sort.Ints(nums)
    for i := 0; i < len(nums); i++{
        if i > 0 && nums[i] == nums[i-1]{
            continue
        }

        left, right := i+1, len(nums)-1
        CHECK:
        for left < right{
            for left > i+1 && nums[left] == nums[left-1]{
                left++
                continue CHECK
            }

            for right < len(nums) - 1 && nums[right] == nums[right+1]{
                right--
                continue CHECK
            }

            if nums[i] + nums[left] + nums[right] == 0{
                res = append(res, []int{nums[i], nums[left], nums[right]})
                left++
                right--
            }else if nums[i] + nums[left] + nums[right] < 0{
                left++
            }else{
                right--
            }
        }
    }

    return res
}

import "sort"

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    length := len(nums)
    res := [][]int{}
    for i := 0; i < length; i++{
        if i > 0 && nums[i] == nums[i-1]{
            continue
        }

        for j := i+1; j < length; j++{
            if j > i+1 && nums[j] == nums[j-1]{
                continue
            }

            left, right := j+1, length-1
            CHECK:
            for left < right{
                for left > j+1 && nums[left] == nums[left-1]{
                    left++
                    continue CHECK
                }
                for right < length-1 && nums[right] == nums[right+1]{
                    right--
                    continue CHECK
                }
                sum := nums[i] + nums[j] + nums[left] + nums[right]
                if sum > target{
                    right--
                }else if sum < target{
                    left++
                }else{
                    res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
                    left++
                    right--
                }

            }
        }
    }
    return res
}

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    m := make(map[int]int, len(nums1)*len(nums2))
    for _, v := range nums1{
        for _, v2 := range nums2{
            m[v+v2] ++
        }
    }

    res := 0
    for _, v3 := range nums3{
        for _, v4 := range nums4{
            res += m[0-v3-v4]
        }
    }
    return res
}

func reverseString(s []byte)  {
    left, right := 0, len(s)-1
    for left < right{
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}

func reverseStr(s string, k int) string {
    b := []byte(s)
    length := len(b)
    for i := 0; i < length; i += 2*k{
        end := i+k
        if end > length{
            end = length
        }
        reverse(b[i:end])
    }
    return string(b)

}

func reverse(s []byte) {
    left, right := 0, len(s)-1
    for left < right{
        s[left], s[right] =  s[right], s[left]
        left++
        right--
    }
}

func replaceSpace(s string) string {
    count := 0
    for _, v := range s{
        if v == ' '{
            count++
        }
    }
    b := make([]byte, len(s)+2*count)
    right := 0
    for _, v := range s{
        if v == ' '{
            b[right] = '%'
            b[right+1] = '2'
            b[right+2] = '0'
            right += 3
            continue
        }
        b[right] = byte(v)
        right++
    }
    return string(b)
}

func replaceSpace(s string) string {
    b := []byte(s)
    left := len(b)-1
    count := 0
    for i := 0; i <= left; i++{
        if b[i] == byte(' '){
            count++
        }
    }
    padding := make([]byte, 2*count)
    b = append(b, padding...)
    right := len(b)-1
    for left < right{
        if b[left] == byte(' '){
            b[right] = '0'
            b[right-1] = '2'
            b[right-2] = '%'
            right -= 3
            left--
            continue
        }
        b[right] = b[left]
        right--
        left--
    }
    return string(b)
}

// method 1
func reverseWords(s string) string {
    ss := strings.Fields(s)
	reverse(ss)
	return strings.Join(ss, " ")
}

func reverse(m []string) {
    i := 0
    j := len(m)-1
    for i < j {
        m[i], m[j] = m[j], m[i]
        i++
        j--
    }
}

// method 2
func reverseWords(s string) string {
    b := []byte(s)
    b = removeExtraSpaces(b)
    reverse(b)
    wordstart := 0
    for k, v := range b{
        if  k == len(b)-1{
            reverse(b[wordstart:])
        }
        if v == ' ' {
            reverse(b[wordstart: k])
            wordstart = k + 1
        }
    }
    return string(b)
}

func removeExtraSpaces(b []byte) []byte{
    fast := 0
    for fast < len(b) && b[fast] == ' '{
        fast++
    }

    slow := 0
    for ; fast < len(b); fast++{
        cond1 := b[fast] != ' '
        cond2 := b[fast] == ' ' && fast > 0 && b[fast-1] != ' '
        if cond1 || cond2{
            b[slow] = b[fast]
            slow++
        }
    }

    if b[slow-1] == ' '{
        return b[:slow-1]
    }else{
        return b[:slow]
    }
}

// 方法一：KMP

// H: AABAACAABAACAABAAD
// N: AABAACAABAAD
// i是haystack下标，j是needle的下标

// H[0:11] == N[0:11], 前11次比较匹配
// 第12次比较不匹配，即i = j = 11时，H[11] != N[11]

// 由 j = next[j-1] = next(11-1) = 5，表示前5次比较是匹配的
// 也就是 H[6:11] == N[0:5]

// 因此可以直接从H[11] 与 N[5]开始比较，H的遍历过程没有回退
// 复杂度O(n)

func strStr(haystack string, needle string) int {
    next := getNext(needle)
    j := 0
    for i := 0; i < len(haystack); i++ {
        for j > 0 && haystack[i] != needle[j] {
            j = next[j-1]
        }

        if haystack[i] == needle[j] {
            j++
        }

        if j == len(needle) {
            return i - j + 1
        }
    }
    return -1
}

// needle:  a d c a d d e
// next:    0 0 0 1 2 0 0

// needle:  a a b a a f
// next:    0 1 0 1 2 0
func getNext(needle string) []int {
    next := make([]int, len(needle))
    next[0] = 0
    for right := 1; right < len(needle); right++ {
        //
        left := next[right-1]
        for left > 0 && needle[right] != needle[left] {
            left = next[left-1]
        }

        if needle[right] == needle[left] {
            left++
        }

        next[right] = left
    }
    return next
}

// 方法二
func strStr(haystack string, needle string) int {
    if needle == ""{
        return 0
    }
    for i, j := 0, len(needle); j <= len(haystack); i, j = i+1, j+1{
        if haystack[i:j] == needle{
            return i
        }
    }
    return -1
}

func repeatedSubstringPattern(s string) bool {
    for i := 1; i < len(s)/2 + 1; i++{
        if len(s) % i != 0{
            continue
        }
        for j := 1; j < len(s)/i; j++{
            if s[0:i] != s[j*i:j*i+i]{
                break
            }
            // 成功匹配最后一段
            if j == len(s)/i -1 {
                return true
            }
        }
    }
    return false
}

//KMP
func repeatedSubstringPattern(s string) bool {
    if len(s) < 2{
        return false
    }
    next := getNext(s)
    a := next[len(s)-1]  // 最长相同前后缀的长度
    b := len(s) - a // 重复子串长度

    if a > 0 && len(s) % b  == 0{
        return true
    }
    return false
}

func getNext(needle string) []int {
	next := make([]int, len(needle))
	next[0] = 0
	for right := 1; right < len(needle); right++ {
		left := next[right-1]
		for left > 0 && needle[right] != needle[left] {
			left = next[left-1]
		}
		if needle[right] == needle[left] {
			left++
		}
		next[right] = left
	}
	return next
}

func isValid(s string) bool {
    stack := make([]rune, 0)
    for _, v := range s{
        switch v{
            case '(':
                stack = append(stack, ')')
            case '[':
                stack = append(stack, ']')
            case '{':
                stack = append(stack, '}')
            default:
                if len(stack) > 0 && stack[len(stack)-1] == v{
                    stack = stack[:len(stack)-1] // 出栈
                }else{
                    return false
                }
        }
    }
    return len(stack) == 0
}

func removeDuplicates(s string) string {
    stack := make([]rune, 0)
    for _, v := range s{
        if len(stack) > 0 && stack[len(stack)-1] == v{
            stack = stack[:len(stack)-1]
        }else{
            stack = append(stack, v)
        }
    }
    return string(stack)
}

func evalRPN(tokens []string) int {
    var stack []int
    for _, v := range tokens{
        switch v{
            case "+":
                stack[len(stack)-2] = stack[len(stack)-2] + stack[len(stack)-1]
                stack = stack[:len(stack)-1]
            case "-":
                stack[len(stack)-2] = stack[len(stack)-2] - stack[len(stack)-1]
                stack = stack[:len(stack)-1]
            case "*":
                stack[len(stack)-2] = stack[len(stack)-2] * stack[len(stack)-1]
                stack = stack[:len(stack)-1]
            case "/":
                stack[len(stack)-2] = stack[len(stack)-2] / stack[len(stack)-1]
                stack = stack[:len(stack)-1]
            default:
                v2, _ := strconv.Atoi(v)
                stack = append(stack, v2)
        }
    }
    return stack[0]
}

func maxSlidingWindow(nums []int, k int) []int {
    queue := make([]int, 0)
    res := make([]int, 0)
    for i, v := range nums{
        // 处理离开窗口的元素
        if i >= k && nums[i-k] == queue[0]{
            queue = queue[1:]
        }

        // 处理进入窗口的元素
        for len(queue) > 0 && v > queue[len(queue)-1]{
            queue = queue[0:len(queue)-1]
        }
        queue = append(queue, v)

        // 记录窗口最大值
        if i >= k-1 {
            res = append(res, queue[0])
        }
    }
    return res
}

import "sort"

func topKFrequent(nums []int, k int) []int {
    m := make(map[int]int)
    for _, num := range nums{
        m[num]++
    }

    keys := []int{}
    for key, _ := range m{
        keys = append(keys, key)
    }

    sort.Slice(keys, func(i, j int)bool{
        return m[keys[i]] >  m[keys[j]]
    })

    return keys[:k]
}

//type TreeNode struct {
 //    Val int
 //    Left *TreeNode
 //    Right *TreeNode
 //}

// 递归法
func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    var rec func(*TreeNode)
    rec = func(node *TreeNode){
        if node == nil{
            return
        }
        res = append(res, node.Val)
        rec(node.Left)
        rec(node.Right)
    }
    rec(root)
    return res
}

func inorderTraversal(root *TreeNode) []int {
    res := []int{}
    var rec func(*TreeNode)
    rec = func(node *TreeNode){
        if node == nil{
            return
        }
        rec(node.Left)
        res = append(res, node.Val)
        rec(node.Right)
    }
    rec(root)
    return res
}

func postorderTraversal(root *TreeNode) []int {
    res := []int{}
    var rec func(*TreeNode)
    rec = func(node *TreeNode){
        if node == nil{
            return
        }
        rec(node.Left)
        rec(node.Right)
        res = append(res, node.Val)
    }
    rec(root)
    return res
}

// 迭代法
func preorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    stack := make([]*TreeNode, 0)
    if root != nil{
        stack = append(stack, root)
    }
    for len(stack) > 0 {
        // 出栈
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if node != nil{
            // 右入栈
            if node.Right != nil{
                stack = append(stack, node.Right)
            }
            // 左入栈
            if node.Left != nil{
                stack = append(stack, node.Left)
            }
            // 中入栈
            // 再次入栈时后面加一个读标记
            stack = append(stack, node, nil)
        }else{
            // 读取数据
            res = append(res, stack[len(stack)-1].Val)
            stack = stack[:len(stack)-1]
        }
    }
    return res
}

func inorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    stack := make([]*TreeNode, 0)
    if root != nil{
        stack = append(stack, root)
    }
    for len(stack) > 0 {
        // 出栈
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if node != nil{
            // 右入栈
            if node.Right != nil{
                stack = append(stack, node.Right)
            }

            // 中入栈
            // 再次入栈时后面加一个读标记
            stack = append(stack, node, nil)

            // 左入栈
            if node.Left != nil{
                stack = append(stack, node.Left)
            }
        }else{
            res = append(res, stack[len(stack)-1].Val)
            stack = stack[:len(stack)-1]
        }
    }
    return res
}

func inorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    stack := make([]*TreeNode, 0)
    node := root
    for node != nil || len(stack) > 0 {
        for node != nil{
            stack = append(stack, node)
            node = node.Left
        }

        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        res = append(res, node.Val)

        node = node.Right
    }
    return res
}

func postorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    stack := make([]*TreeNode, 0)
    if root != nil{
        stack = append(stack, root)
    }
    for len(stack) > 0 {
        // 出栈
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if node != nil{
            // 再次入栈时后面加一个标记
            stack = append(stack, node, nil)

            if node.Right != nil{
                stack = append(stack, node.Right)
            }

            if node.Left != nil{
                stack = append(stack, node.Left)
            }
        }else{
            res = append(res, stack[len(stack)-1].Val)
            stack = stack[:len(stack)-1]
        }
    }
    return res
}