Posts published in “Tree”

花花酱 LeetCode 173. Binary Search Tree Iterator

By zxi on November 28, 2021

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Example 1:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output

[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); bSTIterator.next(); // return 3 bSTIterator.next(); // return 7 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 9 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 15 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 20 bSTIterator.hasNext(); // return False

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
0 <= Node.val <= 10⁶
At most 10⁵ calls will be made to hasNext, and next.

Follow up:

Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?

Solution: In-order traversal using a stack

Use a stack to simulate in-order traversal.

Each next, we walk to the left most (smallest) node and push all the nodes along the path to the stack.

Then pop the top one t as return val, our next node to explore is the right child of t.

Time complexity: amortized O(1) for next() call.
Space complexity: O(n)

C++

// Author: Huahua

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

class BSTIterator {

public:

BSTIterator(TreeNode* root) : root_(root) {}

int next() {

while (root_) {

s_.push(root_);

root_ = root_->left;

}

TreeNode* t = s_.top(); s_.pop();

root_ = t->right;

return t->val;

}

bool hasNext() {

return (root_ || !s_.empty());

}

private:

TreeNode* root_;

stack<TreeNode*> s_;

};

/**

* Your BSTIterator object will be instantiated and called as such:

* BSTIterator* obj = new BSTIterator(root);

* int param_1 = obj->next();

* bool param_2 = obj->hasNext();

花花酱 LeetCode 199. Binary Tree Right Side View

By zxi on November 28, 2021

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Solution: Pre-order traversal

By using pre-order traversal, the right most node will be the last one to visit in each level.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> rightSideView(TreeNode* root) {

vector<int> ans;

function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int d) {

if (!root) return;

if (ans.size() < d + 1) ans.push_back(0);

ans[d] = root->val;

dfs(root->left, d + 1);

dfs(root->right, d + 1);

};

dfs(root, 0);

return ans;

}

};

花花酱 LeetCode 114. Flatten Binary Tree to Linked List

By zxi on November 27, 2021

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

Solution 1: Recursion

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

Python3

# Author: Huahua

class Solution:

def flatten(self, root: Optional[TreeNode]) -> None:

"""

Do not return anything, modify root in-place instead.

"""

def solve(root: Optional[TreeNode]):

if not root: return None, None

if not root.left and not root.right: return root, root

l_head = l_tail = r_head = r_tail = None

if root.left:

l_head, l_tail = solve(root.left)

if root.right:

r_head, r_tail = solve(root.right)

root.left = None

root.right = l_head or r_head

if l_tail:

l_tail.right = r_head

return root, r_tail or l_tail

return solve(root)[0]

Solution 2: Unfolding

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

Python3

# Author: Huahua

class Solution:

def flatten(self, root: Optional[TreeNode]) -> None:

while root:

if root.left:

prev = root.left

while prev.right: prev = prev.right

prev.right = root.right

root.right = root.left

root.left = None

root = root.right

花花酱 LeetCode 2003. Smallest Missing Genetic Value in Each Subtree

By zxi on November 20, 2021

There is a family tree rooted at 0 consisting of n nodes numbered 0 to n - 1. You are given a 0-indexed integer array parents, where parents[i] is the parent for node i. Since node 0 is the root, parents[0] == -1.

There are 10⁵ genetic values, each represented by an integer in the inclusive range [1, 10⁵]. You are given a 0-indexed integer array nums, where nums[i] is a distinct genetic value for node i.

Return an array ans of length n where ans[i] is the smallest genetic value that is missing from the subtree rooted at node i.

The subtree rooted at a node x contains node x and all of its descendant nodes.

Example 1:

Input: parents = [-1,0,0,2], nums = [1,2,3,4]
Output: [5,1,1,1]
Explanation: The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3] with values [1,2,3,4]. 5 is the smallest missing value.
- 1: The subtree contains only node 1 with value 2. 1 is the smallest missing value.
- 2: The subtree contains nodes [2,3] with values [3,4]. 1 is the smallest missing value.
- 3: The subtree contains only node 3 with value 4. 1 is the smallest missing value.

Example 2:

Input: parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
Output: [7,1,1,4,2,1]
Explanation: The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3,4,5] with values [5,4,6,2,1,3]. 7 is the smallest missing value.
- 1: The subtree contains nodes [1,2] with values [4,6]. 1 is the smallest missing value.
- 2: The subtree contains only node 2 with value 6. 1 is the smallest missing value.
- 3: The subtree contains nodes [3,4,5] with values [2,1,3]. 4 is the smallest missing value.
- 4: The subtree contains only node 4 with value 1. 2 is the smallest missing value.
- 5: The subtree contains only node 5 with value 3. 1 is the smallest missing value.

Example 3:

Input: parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
Output: [1,1,1,1,1,1,1]
Explanation: The value 1 is missing from all the subtrees.

Constraints:

Solution: DFS on a single path

One ancestors of node with value of 1 will have missing values greater than 1. We do a dfs on the path that from node with value 1 to the root.

Time complexity: O(n + max(nums))
Space complexity: O(n + max(nums))

C++

// Author: Huahua

class Solution {

public:

vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {

const int n = parents.size();

vector<int> ans(n, 1);

vector<int> seen(100002);

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

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

g[parents[i]].push_back(i);

function<void(int)> dfs = [&](int u) {

if (seen[nums[u]]++) return;

for (int v : g[u]) dfs(v);

};

int u = find(begin(nums), end(nums), 1) - begin(nums);

for (int l = 1; u < n && u != -1; u = parents[u]) {

dfs(u);

while (seen[l]) ++l;

ans[u] = l;

}

return ans;

}

};

花花酱 LeetCode 2049. Count Nodes With the Highest Score

By zxi on October 26, 2021

There is a binary tree rooted at 0 consisting of n nodes. The nodes are labeled from 0 to n - 1. You are given a 0-indexed integer array parents representing the tree, where parents[i] is the parent of node i. Since node 0 is the root, parents[0] == -1.

Each node has a score. To find the score of a node, consider if the node and the edges connected to it were removed. The tree would become one or more non-empty subtrees. The size of a subtree is the number of the nodes in it. The score of the node is the product of the sizes of all those subtrees.

Return the number of nodes that have the highest score.

Example 1:

Input: parents = [-1,2,0,2,0]
Output: 3
Explanation:
- The score of node 0 is: 3 * 1 = 3
- The score of node 1 is: 4 = 4
- The score of node 2 is: 1 * 1 * 2 = 2
- The score of node 3 is: 4 = 4
- The score of node 4 is: 4 = 4
The highest score is 4, and three nodes (node 1, node 3, and node 4) have the highest score.

Example 2:

Input: parents = [-1,2,0]
Output: 2
Explanation:
- The score of node 0 is: 2 = 2
- The score of node 1 is: 2 = 2
- The score of node 2 is: 1 * 1 = 1
The highest score is 2, and two nodes (node 0 and node 1) have the highest score.

Constraints:

n == parents.length
2 <= n <= 10⁵
parents[0] == -1
0 <= parents[i] <= n - 1 for i != 0
parents represents a valid binary tree.

Solution: Recursion

Write a function that returns the element of a subtree rooted at node.

We can compute the score based on:
1. size of the subtree(s)
2. # of children

Root is a special case whose score is max(c[0], 1) * max(c[1], 1).

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

C++

// Author: Huahua

class Solution {

public:

int countHighestScoreNodes(vector<int>& parents) {

const int n = parents.size();

long high = 0;

int ans = 0;

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

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

tree[parents[i]].push_back(i);

function<int(int)> dfs = [&](int node) -> int {

long c[2] = {0, 0};

for (int i = 0; i < tree[node].size(); ++i)

c[i] = dfs(tree[node][i]);

long score = 0;

if (node == 0) // case #1: root

score = max(c[0], 1l) * max(c[1], 1l);

else if (tree[node].size() == 0) // case #2: leaf

score = n - 1;

else if (tree[node].size() == 1) // case #3: one child

score = c[0] * (n - c[0] - 1);

else // case #4: two children

score = c[0] * c[1] * (n - c[0] - c[1] - 1);

if (score > high) {

high = score;

ans = 1;

} else if (score == high) {

++ans;

}

return 1 + c[0] + c[1];

};

dfs(0);

return ans;

}

};