Skip to content

Instantly share code, notes, and snippets.

@shaqsnake
Last active August 15, 2018 15:00
Show Gist options
  • Save shaqsnake/cdb4f6fd72bef3a368b360626aae46ab to your computer and use it in GitHub Desktop.
Save shaqsnake/cdb4f6fd72bef3a368b360626aae46ab to your computer and use it in GitHub Desktop.
1. Given a m*n girds, find all paths from (0, 0) to (m, n) 2. Get the max depth of a binary tree
package main
import (
"fmt"
)
var res = make([][]point, 0)
type point struct {
x, y int
}
func searchPath(x, y, m, n int, path []point) {
// add (x, y) to path
path = append(path, point{x, y})
// reach the (m, n)
if x == m && y == n {
res = append(res, path)
return
}
if x < m {
searchPath(x+1, y, m, n, path)
}
if y < n {
searchPath(x, y+1, m, n, path)
}
// pop the last (x, y) and return
path = path[:len(path)-1]
return
}
func findAllPath(m, n int) {
path := make([]point, 0)
searchPath(0, 0, m, n, path)
return
}
func main() {
findAllPath(3, 2)
//fmt.Println(res)
for _, path := range res {
fmt.Println(path)
}
}
func maxDepth(node *Node) int {
if node == nil {
return 0
}
return max(maxDepth(node.Left), maxDepth(node.Right)) + 1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment