Posts published in “Leetcode”

花花酱 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

花花酱 LeetCode 671. Second Minimum Node In a Binary Tree

By zxi on September 4, 2017

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:

Input:

/ \

2 5

/ \

5 7

Output: 5

Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input:

/ \

2 2

Output: -1

Explanation: The smallest value is 2, but there isn't any second smallest value.

Solution:

Time complexity O(n), Space complexity O(n)

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

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

* };

class Solution {

public:

int findSecondMinimumValue(TreeNode* root) {

if(!root) return -1;

// return BFS(root);

return DFS(root, root->val);

}

private:

// Time complexity: O(n)

// Space complexity: O(n)

int BFS(TreeNode* root) {

if(!root) return -1;

// Smallest value

int s1 = root->val;

// Sencond smallest value

int s2 = INT_MAX;

bool found = false;

deque<TreeNode*> q;

q.push_back(root);

while(!q.empty()) {

TreeNode* node = q.front();

q.pop_front();

// Keep updating second smallest value

if(node->val > s1 && node->val < s2) {

s2 = node->val;

found = true;

// No need to add it's children into queue

continue;

}

if(!node->left) continue;

q.push_back(node->left);

q.push_back(node->right);

}

return found?s2:-1;

}

// Return the second smallest number in the (sub-tree)

// s1 is the smallest value

int DFS(TreeNode* root, int s1) {

if(!root) return -1;

// If root's value is already grater than s1,

// then all its children's value should be >= s1.

// Thus root's value is the second smallest one.

// No need to visit the

if(root->val > s1) return root->val;

int sl = DFS(root->left, s1);

int sr = DFS(root->right, s1);

if(sl == -1) return sr;

if(sr == -1) return sl;

// Return the smaller one among two subtrees

return min(sl, sr);

}

};

花花酱 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);

}

};

花花酱 LeetCode 241. Different Ways to Add Parentheses

By zxi on September 3, 2017

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input: "2-1-1".

1 2	((2-1)-1) = 0 (2-(1-1)) = 2

Output: [0, 2]

Example 2:

Input: "2*3-4*5"

(2*(3-(4*5))) = -34

((2*3)-(4*5)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Solution:

Running time: 3ms

C++

// Author: Huahua

namespace huahua {

int add(int a, int b) { return a+b; }

int minus(int a, int b) { return a-b; }

int multiply(int a, int b) { return a*b; }

} // namespace huahua

class Solution {

public:

vector<int> diffWaysToCompute(string input) {

return ways(input);

}

private:

const vector<int>& ways(const string& input) {

// Already solved, return the answer

if(m_.count(input)) return m_[input];

// Array for answer of input

vector<int> ans;

// Break the expression at every operator

for(int i=0;i<input.length();++i) {

char op = input[i];

// Split the input by an op

if(op=='+' || op=='-' || op=='*') {

const string left = input.substr(0, i);

const string right = input.substr(i+1);

// Get the solution of left/right sub-expressions

const vector<int>& l = ways(left);

const vector<int>& r = ways(right);

std::function<int(int,int)> f;

switch(op) {

case '+': f = huahua::add; break;

case '-': f = huahua::minus; break;

case '*': f = huahua::multiply; break;

}

// Combine the solution

for(int a : l)

for(int b : r)

ans.push_back(f(a,b));

}

// Single number, e.g. s = "3"

if(ans.empty())

ans.push_back(std::stoi(input));

// memorize the answer for input

m_[input].swap(ans);

return m_[input];

}

unordered_map<string, vector<int>> m_;

};

Python3

# Author: Huahua, 44 ms

class Solution:

def diffWaysToCompute(self, input):

ops = {'+': lambda x, y: x + y,

'-': lambda x, y: x - y,

'*': lambda x, y: x * y}

def ways(s):

ans = []

for i in range(len(s)):

if s[i] in "+-*":

ans += [ops[s[i]](l, r) for l, r in itertools.product(ways(s[0:i]), ways(s[i+1:]))]

if not ans: ans.append(int(s))

return ans

return ways(input)

花花酱 LeetCode 21: Merge Two Sorted Lists

By zxi on September 3, 2017

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution 1: Iterative O(n)

// Author: Huahua

class Solution {

public:

Solution 1: Iterative

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail=&dummy;

while(l1 && l2) {

if(l1->val < l2->val) {

tail->next=l1;

l1=l1->next;

}else{

tail->next=l2;

l2=l2->next;

}

tail=tail->next;

}

if(l1) tail->next = l1;

if(l2) tail->next = l2;

return dummy.next;

}

};

Solution 2: Recursive O(n)

// Author: Huahua

class Solution {

public:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

// If one of the list is emptry, return the other one.

if(!l1 || !l2) return l1 ? l1 : l2;

// The smaller one becomes the head.

if(l1->val < l2->val) {

l1->next = mergeTwoLists(l1->next, l2);

return l1;

} else {

l2->next = mergeTwoLists(l1, l2->next);

return l2;

}

};