Posts published in “Tree”

花花酱 LeetCode 1530. Number of Good Leaf Nodes Pairs

By zxi on July 25, 2020

Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].

Example 4:

Input: root = [100], distance = 1
Output: 0

Example 5:

Input: root = [1,1,1], distance = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 2^10].
Each node’s value is between [1, 100].
1 <= distance <= 10

Solution: Brute Force

Since n <= 1024, and distance <= 10, we can collect all leaf nodes and try all pairs.

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

C++

class Solution {

public:

int countPairs(TreeNode* root, int distance) {

unordered_map<TreeNode*, TreeNode*> parents;

vector<TreeNode*> leaves;

function<void(TreeNode*, TreeNode*)> dfs = [&](TreeNode* c, TreeNode* p) {

if (!c) return;

parents[c] = p;

dfs(c->left, c);

dfs(c->right, c);

if (!c->left && !c->right) leaves.push_back(c);

};

dfs(root, nullptr);

unordered_map<TreeNode*, int> a;

auto isGood = [&](TreeNode* n) -> int {

for (int i = 0; i < distance && n; ++i, n = parents[n])

if (a.count(n) && a[n] + i <= distance) return 1;

return 0;

};

int ans = 0;

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

TreeNode* n1 = leaves[i];

a.clear();

for (int k = 0; k < distance && n1; ++k, n1 = parents[n1])

a[n1] = k;

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

ans += isGood(leaves[j]);

}

return ans;

}

};

Solution 2: Post order traversal

For each node, compute the # of good leaf pair under itself.
1. count the frequency of leaf node at distance 1, 2, …, d for both left and right child.
2. ans += l[i] * r[j] (i + j <= distance) cartesian product
3. increase the distance by 1 for each leaf node when pop
Time complexity: O(n*D^2)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countPairs(TreeNode* root, int distance) {

int ans = 0;

function<vector<int>(TreeNode*)> dfs

= [&](TreeNode* c) -> vector<int> {

// f[i] = number of leaves node at distance i.

vector<int> f(distance + 1);

if (!c) return f;

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

f[0] = 1; // a single leaf node

return f;

}

const vector<int>& l = dfs(c->left);

const vector<int>& r = dfs(c->right);

for (int i = 0; i + 1 <= distance; ++i)

for (int j = 0; i + j + 2 <= distance; ++j)

ans += l[i] * r[j];

for (int i = 0; i < distance; ++i)

f[i + 1] = l[i] + r[i];

return f;

};

dfs(root);

return ans;

}

};

Java

class Solution {

private int D;

private int ans;

public int countPairs(TreeNode root, int distance) {

this.D = distance;

this.ans = 0;

dfs(root);

return ans;

}

private int[] dfs(TreeNode root) {

int[] f = new int[D + 1];

if (root == null) return f;

if (root.left == null && root.right == null) {

f[0] = 1;

return f;

}

int[] fl = dfs(root.left);

int[] fr = dfs(root.right);

for (int i = 0; i + 1 <= D; ++i)

for (int j = 0; i + j + 2 <= D; ++j)

this.ans += fl[i] * fr[j];

for (int i = 0; i < D; ++i)

f[i + 1] = fl[i] + fr[i];

return f;

}

Python3

# Author: Huahua

class Solution:

def countPairs(self, root: TreeNode, D: int) -> int:

def dfs(node):

f = [0] * (D + 1)

if not node: return f, 0

if not node.left and not node.right:

f[0] = 1

return f, 0

fl, pl = dfs(node.left)

fr, pr = dfs(node.right)

pairs = 0

for dl, cl in enumerate(fl):

for dr, cr in enumerate(fr):

if dl + dr + 2 <= D: pairs += cl * cr

for i in range(D):

f[i + 1] = fl[i] + fr[i]

return f, pl + pr + pairs

return dfs(root)[1]

花花酱 LeetCode 1519. Number of Nodes in the Sub-Tree With the Same Label

By zxi on July 18, 2020

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [a_i, b_i], which means there is an edge between nodes a_i and b_i in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the i^th node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.

Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]

Example 4:

1 2	<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa" <strong>Output:</strong> [1,2,1,1,2,1]

Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]

Constraints:

1 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
labels.length == n
labels is consisting of only of lower-case English letters.

Solution: Post order traversal + hashtable

For each label, record the count. When visiting a node, we first record the current count of its label as before, and traverse its children, when done, increment the current count, ans[i] = current – before.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> countSubTrees(int n, vector<vector<int>>& edges,

string_view labels) {

vector<vector<int>> g(n);

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

vector<int> seen(n);

vector<int> count(26);

vector<int> ans(n);

function<void(int)> postOrder = [&](int i) {

if (seen[i]++) return;

int before = count[labels[i] - 'a'];

for (int j : g[i]) postOrder(j);

ans[i] = ++count[labels[i] - 'a'] - before;

};

postOrder(0);

return ans;

}

};

Java

// Author: Huahua

class Solution {

private List<List<Integer>> g;

private String labels;

private int[] ans;

private int[] seen;

private int[] count;

public int[] countSubTrees(int n, int[][] edges, String labels) {

this.g = new ArrayList<List<Integer>>(n);

this.labels = labels;

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

this.g.add(new ArrayList<Integer>());

for (int[] e : edges) {

this.g.get(e[0]).add(e[1]);

this.g.get(e[1]).add(e[0]);

}

this.ans = new int[n];

this.seen = new int[n];

this.count = new int[26];

this.postOrder(0);

return ans;

}

private void postOrder(int i) {

if (this.seen[i]++ > 0) return;

int before = this.count[this.labels.charAt(i) - 'a'];

for (int j : this.g.get(i)) this.postOrder(j);

this.ans[i] = ++this.count[this.labels.charAt(i) - 'a'] - before;

}

Python3

# Author: Huahua

class Solution:

def countSubTrees(self, n: int, edges: List[List[int]],

labels: str) -> List[int]:

g = [[] for _ in range(n)]

for u, v in edges:

g[u].append(v)

g[v].append(u)

seen = [False] * n

count = [0] * 26

ans = [0] * n

def postOrder(i):

if seen[i]: return

seen[i] = True

before = count[ord(labels[i]) - ord('a')]

for j in g[i]: postOrder(j)

count[ord(labels[i]) - ord('a')] += 1

ans[i] = count[ord(labels[i]) - ord('a')] - before

postOrder(0)

return ans

花花酱 LeetCode 662. Maximum Width of Binary Tree

By zxi on July 9, 2020

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Example 1:

Input: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Example 2:

Input: 

          1
         /  
        3    
       / \       
      5   3     

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).

Example 3:

Input: 

          1
         / \
        3   2 
       /        
      5      

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).

Example 4:

Input: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

Solution: DFS

Let us assign an id to each node, similar to the index of a heap. root is 1, left child = parent * 2, right child = parent * 2 + 1. Width = id(right most child) – id(left most child) + 1, so far so good.
However, this kind of id system grows exponentially, it overflows even with long type with just 64 levels. To avoid that, we can remap the id with id – id(left most child of each level).

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

C++

// Author: Huahua

class Solution {

public:

int widthOfBinaryTree(TreeNode* root) {

vector<int> ids; // left most id of each level.

function<int(TreeNode*, int, int)> dfs = [&](TreeNode* node, int d, int id) -> int {

if (!node) return 0;

if (d == ids.size()) ids.push_back(id);

return max({id - ids[d] + 1,

dfs(node->left, d + 1, (id - ids[d]) * 2),

dfs(node->right, d + 1, (id - ids[d]) * 2 + 1)});

};

return dfs(root, 0, 0);

}

};

Java

// Author: Huahua

class Solution {

private List<Integer> ids;

public int widthOfBinaryTree(TreeNode root) {

this.ids = new ArrayList<Integer>();

return dfs(root, 0, 0);

}

private int dfs(TreeNode root, int d, int id) {

if (root == null) return 0;

if (ids.size() == d) ids.add(id);

return Math.max(id - ids.get(d) + 1,

Math.max(this.dfs(root.left, d + 1, (id - ids.get(d)) * 2),

this.dfs(root.right, d + 1, (id - ids.get(d)) * 2 + 1)));

}

Python3

# Author: Huahua

class Solution:

def widthOfBinaryTree(self, root: TreeNode) -> int:

ids = []

def dfs(node: TreeNode, d: int, id: int) -> int:

if not node: return 0

if d == len(ids): ids.append(id)

return max(id - ids[d] + 1,

dfs(node.left, d + 1, (id - ids[d]) * 2),

dfs(node.right, d + 1, (id - ids[d]) * 2 + 1))

return dfs(root, 0, 0)

花花酱 LeetCode 1483. Kth Ancestor of a Tree Node

By zxi on June 15, 2020

You are given a tree with n nodes numbered from 0 to n-1 in the form of a parent array where parent[i] is the parent of node i. The root of the tree is node 0.

Implement the function getKthAncestor(int node, int k) to return the k-th ancestor of the given node. If there is no such ancestor, return -1.

The k-th ancestor of a tree node is the k-th node in the path from that node to the root.

Example:

Input:
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

Output:

[null,1,0,-1]

Explanation: TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]); treeAncestor.getKthAncestor(3, 1); // returns 1 which is the parent of 3 treeAncestor.getKthAncestor(5, 2); // returns 0 which is the grandparent of 5 treeAncestor.getKthAncestor(6, 3); // returns -1 because there is no such ancestor

Constraints:

1 <= k <= n <= 5*10^4
parent[0] == -1 indicating that 0 is the root node.
0 <= parent[i] < n for all 0 < i < n
0 <= node < n
There will be at most 5*10^4 queries.

Solution: LogN ancestors

Build the tree from parent array
Traverse the tree
For each node stores up to logn ancestros, 2^0-th, 2^1-th, 2^2-th, …

When k comes in, each node take the highest bit h out, and query its 2^h’s ancestors with k <- (k – 2^h). There will be at most logk recursive query. When it ends? k == 0, we found the ancestors which is the current node. Or node == 0 and k > 0, we already at root which doesn’t have any ancestors so return -1.

Time complexity:
Construction: O(nlogn)
Query: O(logk)

Space complexity:
O(nlogn)

C++

// Author: Huahua

class TreeAncestor {

public:

TreeAncestor(int n, vector<int>& parent):

g_(n), a_(n) {

for (int i = 1; i < n; ++i) g_[parent[i]].push_back(i);

vector<int> path;

dfs(0, path);

}

int getKthAncestor(int node, int k) {

if (k == 0) return node;

if (node == 0 && k > 0) return -1;

int l = min(31ul - __builtin_clz(k), a_[node].size() - 1);

return getKthAncestor(a_[node][l], k - (1 << l));

}

private:

vector<vector<int>> g_, a_;

void dfs(int node, vector<int>& path) {

for (int i = 1; i <= path.size(); i *= 2)

a_[node].push_back(path[path.size() - i]);

path.push_back(node);

for (int c : g_[node]) dfs(c, path);

path.pop_back();

}

};

DP method

C++

// Author: Huahua

class TreeAncestor {

public:

TreeAncestor(int n, vector<int>& parent):

max_level_(32 - __builtin_clz(n)),

dp_(max_level_, vector<int>(n)) {

dp_[0] = parent;

for (int i = 1; i < max_level_; ++i)

for (int j = 0; j < n; ++j)

dp_[i][j] = dp_[i - 1][j] == -1 ? -1 : dp_[i - 1][dp_[i - 1][j]];

}

int getKthAncestor(int node, int k) {

for (int i = 0; i < max_level_ && node != -1; ++i)

if (k & (1 << i))

node = dp_[i][node];

return node;

}

private:

const int max_level_;

vector<vector<int>> dp_;

};

Solution 2: Binary Search

credit: Ziwu Zhou

Construction: O(n)

Traverse the tree in post order, for each node record its depth and id (visiting order).
For each depth, store all the nodes and their ids.

Query: O(logn)

Get the depth and id of the node, if k > d, return -1.
Use binary search to find the first node at depth[d – k] that has a id greater than the query’s one That node is the k-th ancestor of the node.

C++

// Author: Huahua

class TreeAncestor {

public:

TreeAncestor(int n, vector<int>& parent): g_(n), nodes_(n), levels_(n) {

for (int i = 1; i < n; ++i)

g_[parent[i]].push_back(i);

int id = 0;

dfs(0, 0, id);

}

int getKthAncestor(int node, int k) {

const auto [d, id] = nodes_[node];

if (k > d) return -1;

const auto& ns = levels_[d - k];

return upper_bound(begin(ns), end(ns), pair{id, -1})->second;

}

private:

void dfs(int node, int depth, int& id) {

for (int c : g_[node]) dfs(c, depth + 1, ++id);

levels_[depth].emplace_back(id, node);

nodes_[node] = {depth, id};

}

vector<vector<int>> g_; // p -> {{child}}

vector<vector<pair<int, int>>> levels_; // depth -> {{id, node}}

vector<pair<int, int>> nodes_; // node -> {depth, id}

};

花花酱 LeetCode 1448. Count Good Nodes in Binary Tree

By zxi on May 17, 2020

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Example 1:

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Example 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

Constraints:

The number of nodes in the binary tree is in the range [1, 10^5].
Each node’s value is between [-10^4, 10^4].

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

int goodNodes(TreeNode* root, int max_val = INT_MIN) {

if (!root) return 0;

return goodNodes(root->left, max(max_val, root->val))

+ goodNodes(root->right, max(max_val, root->val))

+ (root->val >= max_val ? 1 : 0);

}

};