AlgoExpert Practice (Recursion, Heap, Tries)

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
     if root == nil || root == p || root == q{
        return root
    }

    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil{
        return root
    }
    if left != nil{
        return left
    }
    return right
}

func solveSudoku(board [][]byte)  {
    var rec func([][]byte)bool
    rec = func(board [][]byte)bool{
        for row := 0; row < 9; row++{
            for col := 0; col < 9; col++{
                if board[row][col] == '.'{ // 找到下一个落子位置
                    for k := '1'; k <= '9'; k++{
                        if isvalid(row, col, byte(k), board){
                            board[row][col] = byte(k)
                            if rec(board){
                                return true
                            }
                            board[row][col] = '.'
                        }
                    }
                    return false
                }
            }
        }
        return true
    }
    rec(board)
}

func isvalid(row, col int, k byte, board [][]byte) bool {
	for i := 0; i < 9; i++ { //行
		if board[row][i] == k {
			return false
		}
	}
	for i := 0; i < 9; i++ { //列
		if board[i][col] == k {
			return false
		}
	}
	//方格
	startrow := (row / 3) * 3
	startcol := (col / 3) * 3
	for i := startrow; i < startrow+3; i++ {
		for j := startcol; j < startcol+3; j++ {
			if board[i][j] == k {
				return false
			}
		}
	}
	return true
}

func siftDown(i, j int, array []int) {
    left := 2*i + 1
    right := 2*i + 2
    swapTo := i
    if left <= j && array[left] > array[swapTo] {
        swapTo = left
    }
    if right <= j && array[right] > array[swapTo] {
        swapTo = right
    }
    if swapTo != i {
        arr[i], arr[swapTo] = arr[swapTo], arr[i]
        siftDown(swapTo, j, array)
    }
}

func siftUp(array []int){
    cur := len(array)-1
    parent := (cur - 1) / 2
    if cur > 0 && array[cur] < array[parent]{
      array[cur], array[parent] = array[parent], array[cur]
      siftUp(array[:parent+1])
    }
}