Posts tagged as “tree”

花花酱 LeetCode 513. Find Bottom Left Tree Value

By zxi on March 5, 2018

题目大意：给你一棵树，返回左下角（最后一行最左面）的节点的值。

https://leetcode.com/problems/find-bottom-left-tree-value/description/

Problem:

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Input:

/ \

1 3

Output:

Example 2:

Input:

/ \

2 3

/ / \

4 5 6

Output:

Note: You may assume the tree (i.e., the given root node) is not NULL.

Solution 1: Inorder traversal with depth info

The first node visited in the deepest row is the answer.

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findBottomLeftValue(TreeNode* root) {

int max_row = -1;

int ans;

dfs(root, 0, max_row, ans);

return ans;

}

private:

void inorder(TreeNode* root, int row, int& max_row, int& ans) {

if (root == nullptr) return;

inorder(root->left, row + 1, max_row, ans);

if (row > max_row) {

ans = root->val;

max_row = row;

}

inorder(root->right, row + 1, max_row, ans);

}

};

Python3

"""

Author: Huahua

Running time: 92 ms

"""

class Solution:

def inorder(self, root, row):

if not root: return

self.inorder(root.left, row + 1)

if row > self.max_row:

self.max_row, self.ans = row, root.val

self.inorder(root.right, row + 1)

def findBottomLeftValue(self, root):

self.ans, self.max_row = 0, -1

self.inorder(root, 0)

return self.ans

花花酱 LeetCode 652. Find Duplicate Subtrees

By zxi on December 31, 2017

652. Find Duplicate SubtreesMedium730151FavoriteShare

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Example 1:

The following are two duplicate subtrees:

2
/
4

and

Therefore, you need to return above trees’ root in the form of a list.

Solution 1: Serialization

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua

// Runtime: 29 ms

class Solution {

public:

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {

unordered_map<string, int> counts;

vector<TreeNode*> ans;

serialize(root, counts, ans);

return ans;

}

private:

string serialize(TreeNode* root, unordered_map<string, int>& counts, vector<TreeNode*>& ans) {

if (!root) return "#";

string key = to_string(root->val) + ","

+ serialize(root->left, counts, ans) + ","

+ serialize(root->right, counts, ans);

if (++counts[key] == 2)

ans.push_back(root);

return key;

}

};

Solution 2: int id for each unique subtree

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

// Runtime: 8 ms

class Solution {

public:

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {

unordered_map<long, pair<int,int>> counts;

vector<TreeNode*> ans;

getId(root, counts, ans);

return ans;

}

private:

int getId(TreeNode* root,

unordered_map<long, pair<int,int>>& counts,

vector<TreeNode*>& ans) {

if (!root) return 0;

long key = (static_cast<long>(static_cast<unsigned>(root->val)) << 32) +

(getId(root->left, counts, ans) << 16) +

getId(root->right, counts, ans);

auto& p = counts[key];

if (p.second++ == 0)

p.first = counts.size();

else if (p.second == 2)

ans.push_back(root);

return p.first;

}

};

花花酱 LeetCode Disjoint set / Union Find Forest SP1

By zxi on November 29, 2017

Disjoint-set/Union-find Forest

Find(x): find the root/cluster-id of x

Union(x, y): merge two clusters

Check whether two elements are in the same set or not in O(1)*.

Find: O(ɑ(n))* ≈ O(1)

Union: O(ɑ(n))* ≈ O(1)

Space: O(n)

Without optimization: Find: O(n)

Two key optimizations:

Path compression: make tree flat
Union by rank: merge low rank tree to high rank one

*: amortized

ɑ(.): inverse Ackermann function

Implementations:

C++

// Author: Huahua

class UnionFindSet {

public:

UnionFindSet(int n) {

ranks_ = vector<int>(n + 1, 0);

parents_ = vector<int>(n + 1, 0);

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

parents_[i] = i;

}

// Merge sets that contains u and v.

// Return true if merged, false if u and v are already in one set.

bool Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

// Meger low rank tree into high rank tree

if (ranks_[pv] < ranks_[pu])

parents_[pv] = pu;

else if (ranks_[pu] < ranks_[pv])

parents_[pu] = pv;

else {

parents_[pv] = pu;

ranks_[pu] += 1;

}

return true;

}

// Get the root of u.

int Find(int u) {

// Compress the path during traversal

if (u != parents_[u])

parents_[u] = Find(parents_[u]);

return parents_[u];

}

private:

vector<int> parents_;

vector<int> ranks_;

};

Java

// Author: Huahua

class UnionFindSet {

private int[] parents_;

private int[] ranks_;

public UnionFindSet(int n) {

parents_ = new int[n + 1];

ranks_ = new int[n + 1];

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

parents_[i] = i;

ranks_[i] = 1;

}

public boolean Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

if (ranks_[pv] > ranks_[pu])

parents_[pu] = pv;

else if (ranks_[pu] > ranks_[pv])

parents_[pv] = pu;

else {

parents_[pv] = pu;

ranks_[pu] += 1;

}

return true;

}

public int Find(int u) {

while (parents_[u] != u) {

parents_[u] = parents_[parents_[u]];

u = parents_[u];

}

return u;

}

Python

"""

Author: Huahua

"""

class UnionFindSet:

def __init__(self, n):

self._parents = [i for i in range(n + 1)]

self._ranks = [1 for i in range(n + 1)]

def find(self, u):

while u != self._parents[u]:

self._parents[u] = self._parents[self._parents[u]]

u = self._parents[u]

return u

def union(self, u, v):

pu, pv = self.find(u), self.find(v)

if pu == pv: return False

if self._ranks[pu] < self._ranks[pv]:

self._parents[pu] = pv

elif self._ranks[pu] > self._ranks[pv]:

self._parents[pv] = pu

else:

self._parents[pv] = pu

self._ranks[pu] += 1

return True

Union-Find Problems

References

花花酱 LeetCode 98. Validate Binary Search Tree

By zxi on November 11, 2017

Problem:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

/ \

1 3

Binary tree [2,1,3], return true.

Example 2:

/ \

2 3

Binary tree [1,2,3], return false.

Solution 1

Traverse the tree and limit the range of each subtree and check whether root’s value is in the range.

Time complexity: O(n)

Space complexity: O(n)

Note: in order to cover the range of -2^31 ~ 2^31-1, we need to use long or nullable integer.

C++/long

class Solution {

public:

bool isValidBST(TreeNode* root) {

return isValidBST(root, LLONG_MIN, LLONG_MAX);

}

private:

bool isValidBST(TreeNode* root, long min_val, long max_val) {

if (!root) return true;

if (root->val <= min_val || root->val >= max_val)

return false;

return isValidBST(root->left, min_val, root->val)

&& isValidBST(root->right, root->val, max_val);

}

};

C++/nullable

class Solution {

public:

bool isValidBST(TreeNode* root) {

return isValidBST(root, nullptr, nullptr);

}

private:

bool isValidBST(TreeNode* root, int* min_val, int* max_val) {

if (!root) return true;

if ((min_val && root->val <= *min_val)

||(max_val && root->val >= *max_val))

return false;

return isValidBST(root->left, min_val, &root->val)

&& isValidBST(root->right, &root->val, max_val);

}

};

Java/nullable

// Author: Huahua

// Running time: 1 ms

class Solution {

public boolean isValidBST(TreeNode root) {

return isValidBST(root, null, null);

}

private boolean isValidBST(TreeNode root, Integer min, Integer max) {

if (root == null) return true;

if ((min != null && root.val <= min)

||(max != null && root.val >= max))

return false;

return isValidBST(root.left, min, root.val)

&& isValidBST(root.right, root.val, max);

}

Solution 2

Do an in-order traversal, the numbers should be sorted, thus we only need to compare with the previous number.

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isValidBST(TreeNode* root) {

prev_ = nullptr;

return inOrder(root);

}

private:

TreeNode* prev_;

bool inOrder(TreeNode* root) {

if (!root) return true;

if (!inOrder(root->left)) return false;

if (prev_ && root->val <= prev_->val) return false;

prev_ = root;

return inOrder(root->right);

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

private TreeNode prev;

public boolean isValidBST(TreeNode root) {

prev = null;

return inOrder(root);

}

private boolean inOrder(TreeNode root) {

if (root == null) return true;

if (!inOrder(root.left)) return false;

if (prev != null && root.val <= prev.val) return false;

prev = root;

return inOrder(root.right);

}

Solution: Recursion

C++

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int maxPathSum(TreeNode* root) {

if (!root) return 0;

int ans = INT_MIN;

maxPathSum(root, ans);

return ans;

}

private:

int maxPathSum(TreeNode* root, int& ans) {

if (!root) return 0;

int l = max(0, maxPathSum(root->left, ans));

int r = max(0, maxPathSum(root->right, ans));

int sum = l + r + root->val;

ans = max(ans, sum);

return max(l, r) + root->val;

}

};

Python3

"""

Author: Huahua

Runtime: 138 ms (< 90.38%)

"""

class Solution(object):

def _maxPathSum(self, root):

if not root: return -sys.maxint

l = max(0, self._maxPathSum(root.left))

r = max(0, self._maxPathSum(root.right))

self.ans = max(self.ans, root.val + l + r)

return root.val + max(l, r)

def maxPathSum(self, root):

self.ans = -sys.maxint

self._maxPathSum(root)

return self.ans

Related Problems:

Posts tagged as “tree”

花花酱 LeetCode 513. Find Bottom Left Tree Value

花花酱 LeetCode 652. Find Duplicate Subtrees

Solution 1: Serialization

C++

C++

花花酱 LeetCode Disjoint set / Union Find Forest SP1

Implementations:

C++

Java

Python

Union-Find Problems

References

花花酱 LeetCode 98. Validate Binary Search Tree

Solution 1

C++/long

C++/nullable

Java/nullable

Solution 2

C++

Java

Related Problem

花花酱 LeetCode 124. Binary Tree Maximum Path Sum

Solution: Recursion

C++

Python3