Algoschool

Explore

Level 1

BST Problems

/**

* Definition for a binary tree node.

* type TreeNode struct {

* Val int

* Left *TreeNode

* Right *TreeNode

* }

func dfs(node *TreeNode, path string, paths *[]string) {

if node == nil {

return

}

val := strconv.Itoa(node.Val)

if path != "" {

val = path + "->" + val

}

if node.Left == nil && node.Right == nil {

*paths = append(*paths, val)

return

}

dfs(node.Left, val, paths)

dfs(node.Right, val, paths)

}

func binaryTreePaths(root *TreeNode) []string {

paths := make([]string, 0)

dfs(root, "", &paths)

return paths

}

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

def dfs(node, level, res):

if node.left is None and node.right is None:

res.append((node.val, level))

if node.left:

dfs(node.left, level + 1, res)

if node.right:

dfs(node.right, level + 1, res)

class Solution:

def deepestLeavesSum(self, root: TreeNode) -> int:

res = []

dfs(root, 0, res)

max_level = 0

for (v, level) in res:

max_level = max(max_level, level)

result = 0

for (v, level) in res:

if level == max_level:

result += v

return result

⁠

https://leetcode.com/problems/maximum-depth-of-binary-tree⁠

⁠

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

def dfs(node, level):

ll = 0

lr = 0

if node.left is not None:

ll = dfs(node.left, level + 1)

if node.right is not None:

lr = dfs(node.right, level + 1)

return max(ll, lr, level)

class Solution:

def maxDepth(self, root: TreeNode) -> int:

if not root:

return 0

return dfs(root, 1)

⁠

https://leetcode.com/problems/number-of-islands/⁠

⁠

DIRS = [(0, 1), (1, 0), (-1, 0), (0, -1)]

def dfs(grid, i, j):

grid[i][j] = '0'

for (ix, jx) in DIRS:

ni, nj = i + ix, j + jx

if ni < 0 or nj < 0 or ni >= len(grid) or nj >= len(grid[ni]):

continue

if grid[ni][nj] == '0':

continue

dfs(grid, ni, nj)

class Solution:

def numIslands(self, grid: List[List[str]]) -> int:

res = 0

for i in range(len(grid)):

for j in range(len(grid[i])):

if grid[i][j] == '1':

res += 1

dfs(grid, i, j)

return res

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.