Posts tagged as “tree”

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

}

};

花花酱 LeetCode 1382. Balance a Binary Search Tree

By zxi on March 15, 2020

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Example 1:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.

Constraints:

The number of nodes in the tree is between 1 and 10^4.
The tree nodes will have distinct values between 1 and 10^5.

Solution: Inorder + recursion

Use inorder traversal to collect a sorted array from BST. And then build a balanced BST from this sorted array in O(n) time.

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* balanceBST(TreeNode* root) {

vector<int> vals;

function<void(TreeNode*)> inorder = [&](TreeNode* root) {

if (!root) return;

inorder(root->left);

vals.push_back(root->val);

inorder(root->right);

};

function<TreeNode*(int, int)> build = [&](int l, int r) {

if (l > r) return (TreeNode*)nullptr;

int m = l + (r - l) / 2;

auto root = new TreeNode(vals[m]);

root->left = build(l, m - 1);

root->right = build(m + 1, r);

return root;

};

inorder(root);

return build(0, vals.size() - 1);

}

};

花花酱 LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

By zxi on March 13, 2020

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Follow up: Solve the problem if repeated values on the tree are allowed.

Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2:

Input: tree = [7], target =  7
Output: 7

Example 3:

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Example 4:

Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5

Example 5:

Input: tree = [1,2,null,3], target = 2
Output: 2

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
The values of the nodes of the tree are unique.
target node is a node from the original tree and is not null.

Solution: Recursion

Traverse both trees in the same order, if original == target, return cloned.

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {

if (!original) return nullptr;

if (original == target) return cloned;

auto l = getTargetCopy(original->left, cloned->left, target);

auto r = getTargetCopy(original->right, cloned->right, target);

return l ? l : r;

}

};

Python3

# Author: Huahua

class Solution:

def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

if not original: return None

if original == target: return cloned

return self.getTargetCopy(original.left, cloned.left, target) or \

self.getTargetCopy(original.right, cloned.right, target)