Posts published in “Tree”

花花酱 LeetCode 653. Two Sum IV – Input is a BST

By zxi on December 29, 2017

题目大意：给你一棵二叉搜索树，返回树中是否存在两个节点的和等于给定的目标值。

Problem:

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input:

/ \

3 6

/ \ \

2 4 7

Target = 9

Output: True

Example 2:

Input:

/ \

3 6

/ \ \

2 4 7

Target = 28

Output: False

Solution:

C++

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

bool findTarget(TreeNode* root, int k) {

vector<int> nums;

inorder(root, nums);

int l = 0;

int r = nums.size() - 1;

while (l < r) {

int sum = nums[l] + nums[r];

if (sum == k) return true;

else if (sum < k)

++l;

else

--r;

}

return false;

}

private:

void inorder(TreeNode* root, vector<int>& nums) {

if (root == nullptr) return;

inorder(root->left, nums);

nums.push_back(root->val);

inorder(root->right, nums);

}

};

花花酱 LeetCode 742. Closest Leaf in a Binary Tree

By zxi on December 12, 2017

Problem:

Given a binary tree where every node has a unique value, and a target key k, find the value of the closest leaf node to target k in the tree.

Here, closest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.

Example 1:

Input:

root = [1, 3, 2], k = 1

Diagram of binary tree:

/ \

3 2

Output: 2 (or 3)

Explanation: Either 2 or 3 is the closest leaf node to the target of 1.

Example 2:

Input:

root = [1], k = 1

Output: 1

Explanation: The closest leaf node is the root node itself.

Example 3:

Input:

root = [1,2,3,4,null,null,null,5,null,6], k = 2

Diagram of binary tree:

/ \

2 3

Output: 3

Explanation: The leaf node with value 3 (and not the leaf node with value 6) is closest to the node with value 2.

Note:

root represents a binary tree with at least 1 node and at most 1000 nodes.
Every node has a unique node.val in range [1, 1000].
There exists some node in the given binary tree for which node.val == k.

题目大意:

给你一棵树，每个节点的值都不相同。

给定一个节点值，让你找到离这个节点距离最近的叶子节点的值。

Idea:

Shortest path from source to any leaf nodes in a undirected unweighted graph.

问题转换为在无向/等权重的图中找一条从起始节点到任意叶子节点最短路径。

Solution:

C++ / DFS + BFS

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

int findClosestLeaf(TreeNode* root, int k) {

graph_.clear();

start_ = nullptr;

buildGraph(root, nullptr, k);

queue<TreeNode*> q;

q.push(start_);

unordered_set<TreeNode*> seen;

while (!q.empty()) {

int size = q.size();

while (size-->0) {

TreeNode* curr = q.front();

q.pop();

seen.insert(curr);

if (!curr->left && !curr->right) return curr->val;

for (TreeNode* node : graph_[curr])

if (!seen.count(node)) q.push(node);

}

return 0;

}

private:

void buildGraph(TreeNode* node, TreeNode* parent, int k) {

if (!node) return;

if (node->val == k) start_ = node;

if (parent) {

graph_[node].push_back(parent);

graph_[parent].push_back(node);

}

buildGraph(node->left, node, k);

buildGraph(node->right, node, k);

}

unordered_map<TreeNode*, vector<TreeNode*>> graph_;

TreeNode* start_;

};

花花酱 LeetCode 745. Prefix and Suffix Search

By zxi on December 11, 2017

Link: https://leetcode.com/problems/prefix-and-suffix-search/description/

Problem:

Given many words, words[i] has weight i.

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.

Examples:

Input:

WordFilter(["apple"])

WordFilter.f("a", "e") // returns 0

WordFilter.f("b", "") // returns -1

Note:

words has length in range [1, 15000].
For each test case, up to words.length queries WordFilter.f may be made.
words[i] has length in range [1, 10].
prefix, suffix have lengths in range [0, 10].
words[i] and prefix, suffix queries consist of lowercase letters only.

Idea:

Construct all possible filters

Solution1:

C++

Time complexity: O(NL^3 + QL) where N is the number of words, L is the max length of the word, Q is the number of queries.

Space complexity: O(NL^3)

// Author: Huahua

// Runtime: 482 ms

class WordFilter {

public:

WordFilter(const vector<string>& words) {

int index = 0;

for (const string& word : words) {

int n = word.length();

string prefix;

for (int i = 0; i <= n; ++i) {

if (i > 0) prefix += word[i - 1];

string suffix;

for (int j = n; j >= 0; --j) {

if (j != n) suffix = word[j] + suffix;

const string key = prefix + "_" + suffix;

filters_[key] = index;

}

++index;

}

int f(string prefix, string suffix) {

const string key = prefix + "_" + suffix;

auto it = filters_.find(key);

if (it != filters_.end()) return it->second;

return -1;

}

private:

unordered_map<string, int> filters_;

};

Version #2

// Author: Huahua

// Runtime: 499 ms

class WordFilter {

public:

WordFilter(const vector<string>& words) {

int index = 0;

for (const string& word : words) {

int n = word.length();

vector<string> prefixes(n + 1, "");

vector<string> suffixes(n + 1, "");

for (int i = 0; i < n; ++i) {

prefixes[i + 1] = prefixes[i] + word[i];

suffixes[i + 1] = word[n - i - 1] + suffixes[i];

}

for (const string& prefix : prefixes)

for (const string& suffix : suffixes)

filters_[prefix + "_" + suffix] = index;

++index;

}

int f(string prefix, string suffix) {

const string key = prefix + "_" + suffix;

auto it = filters_.find(key);

if (it != filters_.end()) return it->second;

return -1;

}

private:

unordered_map<string, int> filters_;

};

Solution 2:

C++ / Trie

Time complexity: O(NL^2 + QL) where N is the number of words, L is the max length of the word, Q is the number of queries.

Space complexity: O(NL^2)

// Author: Huahua

// Runtime: 572 ms

class Trie {

public:

/** Initialize your data structure here. */

Trie(): root_(new TrieNode()) {}

/** Inserts a word into the trie. */

void insert(const string& word, int index) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a'])

p->children[c - 'a'] = new TrieNode();

p = p->children[c - 'a'];

// Update index

p->index = index;

}

p->is_word = true;

}

/** Returns the index of word that has the prefix. */

int startsWith(const string& prefix) const {

auto node = find(prefix);

if (!node) return -1;

return node->index;

}

private:

struct TrieNode {

TrieNode():index(-1), is_word(false), children(27, nullptr){}

~TrieNode() {

for (TrieNode* child : children)

if (child) delete child;

}

int index;

int is_word;

vector<TrieNode*> children;

};

const TrieNode* find(const string& prefix) const {

const TrieNode* p = root_.get();

for (const char c : prefix) {

p = p->children[c - 'a'];

if (p == nullptr) break;

}

return p;

}

std::unique_ptr<TrieNode> root_;

};

class WordFilter {

public:

WordFilter(vector<string> words) {

for (int i = 0; i < words.size(); ++i) {

const string& w = words[i];

string key = "{" + w;

trie_.insert(key, i);

for (int j = 0; j < w.size(); ++j) {

key = w[w.size() - j - 1] + key;

trie_.insert(key, i);

}

int f(string prefix, string suffix) {

return trie_.startsWith(suffix + "{" + prefix);

}

private:

Trie trie_;

};

Related Problems:

花花酱 LeetCode 530. Minimum Absolute Difference in BST

By zxi on December 9, 2017

Link

Problem:

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

Output:

Explanation:

The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

Idea:

Sorting via inorder traversal gives us sorted values, compare current one with previous one to reduce space complexity from O(n) to O(h).

Solution:

C++ O(n) space

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int getMinimumDifference(TreeNode* root) {

std::vector<int> sorted;

inorder(root, sorted);

int min_diff = sorted.back();

for (int i = 1; i < sorted.size(); ++i)

min_diff = min(min_diff, sorted[i] - sorted[i - 1]);

return min_diff;

}

private:

void inorder(TreeNode* root, std::vector<int>& sorted) {

if (!root) return;

inorder(root->left, sorted);

sorted.push_back(root->val);

inorder(root->right, sorted);

}

};

C++ O(h) space

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

int getMinimumDifference(TreeNode* root) {

min_diff_ = INT_MAX;

prev_ = nullptr;

inorder(root);

return min_diff_;

}

private:

void inorder(TreeNode* root) {

if (!root) return;

inorder(root->left);

if (prev_) min_diff_ = min(min_diff_, root->val - *prev_);

prev_ = &root->val;

inorder(root->right);

}

int* prev_;

int min_diff_;

};

Java

// Author: Huahua

// Runtime: 16 ms

class Solution {

public int getMinimumDifference(TreeNode root) {

prev_ = null;

min_diff_ = Integer.MAX_VALUE;

inorder(root);

return min_diff_;

}

private void inorder(TreeNode root) {

if (root == null) return;

inorder(root.left);

if (prev_ != null) min_diff_ = Math.min(min_diff_, root.val - prev_);

prev_ = root.val;

inorder(root.right);

}

private Integer prev_;

private int min_diff_;

}

Python

"""

Author: Huahua

Runtime: 92 ms

"""

class Solution(object):

def getMinimumDifference(self, root):

def inorder(root):

if not root: return

inorder(root.left)

if self.prev is not None: self.min_diff = min(self.min_diff, root.val - self.prev)

self.prev = root.val

inorder(root.right)

self.prev = None

self.min_diff = float('inf')

inorder(root)

return self.min_diff

Related Problems:

[解题报告] LeetCode 98. Validate Binary Search Tree

花花酱 LeetCode 113. Path Sum II

By zxi on November 27, 2017

Problem:

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

/ \

4 8

/ / \

11 13 4

/ \ / \

7 2 5 1

return

[

[5,4,11,2],

[5,8,4,5]

]

Idea:

Recursion

Solution:

C++

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

vector<vector<int>> pathSum(TreeNode* root, int sum) {

vector<vector<int>> ans;

vector<int> curr;

pathSum(root, sum, curr, ans);

return ans;

}

private:

void pathSum(TreeNode* root, int sum, vector<int>& curr, vector<vector<int>>& ans) {

if(root==nullptr) return;

if(root->left==nullptr && root->right==nullptr) {

if(root->val == sum) {

ans.push_back(curr);

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

}

return;

}

curr.push_back(root->val);

int new_sum = sum - root->val;

pathSum(root->left, new_sum, curr, ans);

pathSum(root->right, new_sum, curr, ans);

curr.pop_back();

}

};

Related Problems: