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 153. Find Minimum in Rotated Sorted Array

By zxi on September 6, 2017

Problem:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Idea:

Divide and conquer.

Evenly Split the array into two sub-arrays, and find the minimums of them, return the smaller one.

findMin(a[0..n]) = min(findMin(a[0..n/2], a[n/2..n])

Key property:

One of the sub-array will be a sorted array, it takes O(1) to find the minimal element, just the first element.

Time complexity:

T(n) = O(1) + T(n/2) = O(logn)

Solution:

// Author: Huahua

class Solution {

public:

int findMin(vector<int> &num) {

return findMin(num, 0, num.size()-1);

}

private:

int findMin(const vector<int>& num, int l, int r)

{

// Only 1 or 2 elements

if (l+1 >= r) return min(num[l], num[r]);

// Sorted

if (num[l] < num[r]) return num[l];

int mid = l + (r-l)/2;

return min(findMin(num, l, mid-1),

findMin(num, mid, r));

}

};

花花酱 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 654. Maximum Binary Tree

By zxi on September 4, 2017

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5]

Output: return the tree root node representing the following tree:

/ \

3 5

\ /

2 0

Idea:

Recursion

Solution:

With copy

Time complexity: O(nlogn) ~ O(n^2)

Space complexity: O(nlogn) ~ O(n^2)

running time 79ms

// Author: Huahua

class Solution {

public:

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

if(nums.empty()) return nullptr;

auto it = std::max_element(nums.begin(), nums.end());

TreeNode* root=new TreeNode(*it);

vector<int> left(nums.begin(), it);

vector<int> right(it+1, nums.end());

root->left = constructMaximumBinaryTree(left);

root->right = constructMaximumBinaryTree(right);

return root;

}

Without copy

Time complexity: O(nlogn) ~ O(n^2)

Space complexity: O(logn) ~ O(n)

running time 66ms

// Author: Huahua

class Solution {

public:

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

return makeMBT(nums, 0, nums.size());

}

private:

TreeNode* makeMBT(const vector<int>& nums, int begin, int end) {

if(begin>=end) return nullptr;

auto it = std::max_element(nums.begin() + begin, nums.begin() + end);

TreeNode* root=new TreeNode(*it);

int index = it - nums.begin();

root->left = makeMBT(nums, begin, index);

root->right = makeMBT(nums, index+1, end);

return root;

}

};

花花酱 LeetCode 669. Trim a Binary Search Tree

By zxi on September 4, 2017

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:

Input:

/ \

0 2

L = 1

R = 2

Output:

Example 2:

Input:

/ \

0 4

L = 1

R = 3

Output:

This problem can be solved with recursion

There 3 cases in total depends on the root value and L, R

Time complexity: O(n)

Space complexity: O(1)

Solution:

// Author: Huahua

class Solution {

public:

// No cleanup -> memory leak

TreeNode* trimBST(TreeNode* root, int L, int R) {

if(!root) return nullptr;

// val not in range, return the left/right subtrees

if(root->val < L) return trimBST(root->right, L, R);

if(root->val > R) return trimBST(root->left, L, R);

// val in [L, R], recusively trim left/right subtrees

root->left = trimBST(root->left, L, R);

root->right = trimBST(root->right, L, R);

return root;

}

};

The previous solution has potential memory leak for languages without garbage collection.

Here’s the full program to delete trimmed nodes.

// Author: Huahua

#include <iostream>

using namespace std;

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

// With cleanup -> no memory leak

TreeNode*& trimBST(TreeNode*& root, int L, int R) {

if(!root) return root;

if(root->val < L) {

auto& result = trimBST(root->right, L, R);

deleteTree(root->left);

delete root;

root=nullptr;

return result;

} else if(root->val > R) {

auto& result = trimBST(root->left, L, R);

deleteTree(root->right);

delete root;

root=nullptr;

return result;

} else {

// recusively trim left/right subtrees

root->left = trimBST(root->left, L, R);

root->right = trimBST(root->right, L, R);

return root;

}

void deleteTree(TreeNode* &root) {

if(!root) return;

deleteTree(root->left);

deleteTree(root->right);

delete root;

root=nullptr;

}

};

void PrintTree(TreeNode* root) {

if(!root) {

cout<<"null ";

return;

};

if(!root->left && !root->right) {

cout<<root->val<<" ";

} else {

cout<<root->val<<" ";

PrintTree(root->left);

PrintTree(root->right);

}

int main()

{

TreeNode* root=new TreeNode(2);

root->left=new TreeNode(1);

root->right=new TreeNode(3);

PrintTree(root);

std::cout<<std::endl;

TreeNode* t = Solution().trimBST(root, 3, 4);

PrintTree(t);

std::cout<<std::endl;

// Original root was deleted

PrintTree(root);

std::cout<<std::endl;

return 0;

}

Example output

2 1 3

null

Huahua's Tech Road

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

花花酱 Leetcode 153. Find Minimum in Rotated Sorted Array

花花酱 LeetCode 79. Word Search

C++

Python

花花酱 LeetCode 654. Maximum Binary Tree

花花酱 LeetCode 669. Trim a Binary Search Tree