花花酱 LeetCode 865. Smallest Subtree with all the Deepest Nodes

By zxi on July 8, 2018

Problem

Given a binary tree rooted at root, the depth of each node is the shortest distance to the root.

A node is deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is that node, plus the set of all descendants of that node.

Return the node with the largest depth such that it contains all the deepest nodes in it’s subtree.

Example 1:

Input: [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation:



We return the node with value 2, colored in yellow in the diagram.
The nodes colored in blue are the deepest nodes of the tree.
The input "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" is a serialization of the given tree.
The output "[2, 7, 4]" is a serialization of the subtree rooted at the node with value 2.
Both the input and output have TreeNode type.

Note:

The number of nodes in the tree will be between 1 and 500.
The values of each node are unique.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

TreeNode* subtreeWithAllDeepest(TreeNode* root) {

return depth(root).second;

}

private:

pair<int, TreeNode*> depth(TreeNode* root) {

if (root == nullptr)

return {-1, nullptr};

auto l = depth(root->left);

auto r = depth(root->right);

int dl = l.first;

int dr = r.first;

return { max(dl, dr) + 1,

dl == dr ? root : (dl > dr) ? l.second : r.second};

}

};

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

TreeNode* subtreeWithAllDeepest(TreeNode* root) {

TreeNode* ans;

depth(root, &ans);

return ans;

}

private:

int depth(TreeNode* root, TreeNode** s) {

if (root == nullptr)

return -1;

TreeNode* sl;

TreeNode* sr;

int l = depth(root->left, &sl);

int r = depth(root->right, &sr);

*s = (l == r) ? root : ((l > r) ? sl : sr);

return max(l, r) + 1;

}

};

Python3

"""

Author: Huahua

Running time: 40 ms

"""

class Solution:

def subtreeWithAllDeepest(self, root):

def solve(root):

if not root: return (-1, None)

dl, sl = solve(root.left)

dr, sr = solve(root.right)

if dl == dr: return (dl + 1, root)

return (dl + 1, sl) if dl > dr else (dr + 1, sr)

return solve(root)[1]

花花酱 LeetCode 572. Subtree of Another Tree

By zxi on March 19, 2018

Problem

题目大意：判断一棵树是不是另外一棵树的子树。

https://leetcode.com/problems/subtree-of-another-tree/description/

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

/ \

4 5

/ \

1 2

Given tree t:

/ \

1 2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:

/ \

4 5

/ \

1 2

Given tree t:

/ \

1 2

Return false.

Solution: Recursion

Time complexity: O(max(n, m))

Space complexity: O(max(n, m))

C++

// Author: Huahua

// Running time: 29 ms

class Solution {

public:

bool isSubtree(TreeNode* s, TreeNode* t) {

if (t == nullptr) return true;

if (s == nullptr) return false;

if (isSameTree(s, t)) return true;

return isSubtree(s->left, t) || isSubtree(s->right, t);

}

private:

bool isSameTree(TreeNode* s, TreeNode* t) {

if (s == nullptr && t == nullptr) return true;

if (s == nullptr || t == nullptr) return false;

return (s->val == t->val)

&& isSameTree(s->left, t->left)

&& isSameTree(s->right, t->right);

}

};

Related Problems

花花酱 LeetCode 508. Most Frequent Subtree Sum

By zxi on March 2, 2018

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Examples 1
Input:

/ \

2 -3

return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2
Input:

/ \

2 -5

return [2], since 2 happens twice, however -5 only occur once.

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

vector<int> findFrequentTreeSum(TreeNode* root) {

unordered_map<int, int> freqs;

int max_freq = -1;

vector<int> ans;

(void)treeSum(root, freqs, max_freq, ans);

return ans;

}

private:

int treeSum(TreeNode* root, unordered_map<int, int>& freqs, int& max_freq, vector<int>& ans) {

if (!root) return 0;

int sum = root->val +

treeSum(root->left, freqs, max_freq, ans) +

treeSum(root->right, freqs, max_freq, ans);

int freq = ++freqs[sum];

if (freq > max_freq) {

max_freq = freq;

ans.clear();

}

if (freq == max_freq)

ans.push_back(sum);

return sum;

}

};

Python

"""

Author: Huahua

Running time: 72 ms (beats 100%)

"""

class Solution:

def findFrequentTreeSum(self, root):

if not root: return []

def treeSum(root):

if not root: return 0

s = root.val + treeSum(root.left) + treeSum(root.right)

f[s] += 1

return s

f = collections.Counter()

treeSum(root)

max_freq = max(f.values())

return [s for s in f.keys() if f[s] == max_freq]

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

}

};

Posts tagged as “subtree”

花花酱 LeetCode 865. Smallest Subtree with all the Deepest Nodes

Problem

Solution: Recursion

花花酱 LeetCode 572. Subtree of Another Tree

Problem

Solution: Recursion

Related Problems

花花酱 LeetCode 508. Most Frequent Subtree Sum

花花酱 LeetCode 652. Find Duplicate Subtrees

Solution 1: Serialization

C++

C++