DFS Archives - Page 19 of 19 - Huahua's Tech Road

花花酱 LeetCode 637. Average of Levels in Binary Tree

By zxi on September 7, 2017

Problem:

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

Input:

/ \

9 20

/ \

15 7

Output: [3, 14.5, 11]

Explanation:

The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.

Hence return [3, 14.5, 11].

Time Complexity:

O(n)

Space Complexity:

O(h)

Solution 1:

BFS

// Author: Huahua

class Solution {

public:

vector<double> averageOfLevels(TreeNode* root) {

if(root == nullptr) return {};

vector<double> ans;

vector<TreeNode*> curr, next;

curr.push_back(root);

// process every level one by one

while(!curr.empty()) {

long long sum = 0;

for(const auto& node : curr) {

sum += node->val;

if (node->left) next.push_back(node->left);

if (node->right) next.push_back(node->right);

}

ans.push_back(static_cast<double>(sum) / curr.size());

curr.swap(next);

next.clear();

}

return ans;

}

};

Solution 2:

DFS

// Author: Huahua

class Solution {

public:

vector<double> averageOfLevels(TreeNode* root) {

if(root == nullptr) return {};

vector<pair<long long, int>> sum_count;

vector<double> ans;

preorder(root, 0, sum_count);

for(const auto& p : sum_count)

ans.push_back(static_cast<double>(p.first) / p.second);

return ans;

}

private:

void preorder(TreeNode* root, int depth, vector<pair<long long, int>>& sum_count) {

if(root == nullptr) return;

if(depth>=sum_count.size()) sum_count.push_back({0,0});

sum_count[depth].first += root->val;

++sum_count[depth].second;

preorder(root->left, depth+1, sum_count);

preorder(root->right, depth+1, sum_count);

}

};

Related Problems:

[解题报告] LeetCode 102. Binary Tree Level Order Traversal

花花酱 LeetCode 79. Word Search

By zxi on September 6, 2017

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[

['A','B','C','E'],

['S','F','C','S'],

['A','D','E','E']

]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Idea:

Search, depth first search

Solution:

C++

class Solution {

public:

bool exist(vector<vector<char>> &board, string word) {

if(board.size()==0) return false;

h = board.size();

w = board[0].size();

for(int i=0;i<w;i++)

for(int j=0;j<h;j++)

if(search(board, word, 0, i, j)) return true;

return false;

}

bool search(vector<vector<char>> &board,

const string& word, int d, int x, int y) {

if(x<0 || x==w || y<0 || y==h || word[d] != board[y][x])

return false;

// Found the last char of the word

if(d==word.length()-1)

return true;

char cur = board[y][x];

board[y][x] = 0;

bool found = search(board, word, d+1, x+1, y)

|| search(board, word, d+1, x-1, y)

|| search(board, word, d+1, x, y+1)

|| search(board, word, d+1, x, y-1);

board[y][x] = cur;

return found;

}

private:

int w;

int h;

};

Python

# Author: Huahua, running time: 216 ms

class Solution:

def exist(self, board: List[List[str]], word: str) -> bool:

if not board: return False

h, w = len(board), len(board[0])

def search(d: int, x: int, y: int) -> bool:

if x < 0 or x == w or y < 0 or y == h or word[d] != board[y][x]:

return False

if d == len(word) - 1: return True

cur = board[y][x]

board[y][x] = ''

found = search(d + 1, x + 1, y) or search(d + 1, x - 1, y) or search(d + 1, x, y + 1) or search(d + 1, x, y - 1)

board[y][x] = cur

return found

return any(search(0, j, i) for i in range(h) for j in range(w))

花花酱 LeetCode 102. Binary Tree Level Order Traversal

By zxi on September 4, 2017

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

/ \

9 20

/ \

15 7

return its level order traversal as:

[

[3],

[9,20],

[15,7]

]

Solution 1: BFS O(n)

class Solution {

public:

vector<vector<int>> levelOrder(TreeNode* root) {

if(!root) return {};

vector<vector<int>> ans;

vector<TreeNode*> curr,next;

curr.push_back(root);

while(!curr.empty()) {

ans.push_back({});

for(TreeNode* node : curr) {

ans.back().push_back(node->val);

if(node->left) next.push_back(node->left);

if(node->right) next.push_back(node->right);

}

curr.swap(next);

next.clear();

}

return ans;

}

};

Solution 2: DFS O(n)

class Solution {

public:

vector<vector<int>> levelOrder(TreeNode* root) {

vector<vector<int>> ans;

DFS(root, 0 /* depth */, ans);

return ans;

}

private:

void DFS(TreeNode* root, int depth, vector<vector<int>>& ans) {

if(!root) return;

// Works with pre/in/post order

while(ans.size()<=depth) ans.push_back({});

ans[depth].push_back(root->val); // pre-order

DFS(root->left, depth+1, ans);

DFS(root->right, depth+1, ans);

}

};

Posts tagged as “DFS”

花花酱 LeetCode 637. Average of Levels in Binary Tree

花花酱 LeetCode 79. Word Search

C++

Python

花花酱 LeetCode 102. Binary Tree Level Order Traversal