Posts tagged as “tree”

花花酱 LeetCode 1315. Sum of Nodes with Even-Valued Grandparent

By zxi on January 11, 2020

Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A grandparent of a node is the parent of its parent, if it exists.)

If there are no nodes with an even-valued grandparent, return 0.

Example 1:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Constraints:

The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

int sumEvenGrandparent(TreeNode* root, int p = 1, int gp = 1) {

if (!root) return 0;

return sumEvenGrandparent(root->left, root->val, p)

+ sumEvenGrandparent(root->right, root->val, p)

+ (gp & 1 ? 0 : root->val);

}

};

花花酱 LeetCode 1305. All Elements in Two Binary Search Trees

By zxi on December 29, 2019

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

Each tree has at most 5000 nodes.
Each node’s value is between [-10^5, 10^5].

Solution: Inorder traversal + Merge Sort

Time complexity: O(t1 + t2)
Space complexity: O(t1 + t2)

C++

// Author: Huahua

class Solution {

public:

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {

function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) {

if (!root) return;

inorder(root->left, t);

t.push_back(root->val);

inorder(root->right, t);

};

vector<int> t1;

vector<int> t2;

inorder(root1, t1);

inorder(root2, t2);

vector<int> m;

int i = 0;

int j = 0;

while (m.size() != t1.size() + t2.size()) {

if (j == t2.size()) m.push_back(t1[i++]);

else if (i == t1.size()) m.push_back(t2[j++]);

else m.push_back(t1[i] < t2[j] ? t1[i++] : t2[j++]);

}

return m;

}

};

C++/STL

// Author: Huahua

class Solution {

public:

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {

function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) {

if (!root) return;

inorder(root->left, t);

t.push_back(root->val);

inorder(root->right, t);

};

vector<int> t1;

vector<int> t2;

inorder(root1, t1);

inorder(root2, t2);

vector<int> m;

std::merge(begin(t1), end(t1), begin(t2), end(t2), back_inserter(m));

return m;

}

};

花花酱 LeetCode 1273. Delete Tree Nodes

By zxi on November 30, 2019

A tree rooted at node 0 is given as follows:

The number of nodes is nodes;
The value of the i-th node is value[i];
The parent of the i-th node is parent[i].

Remove every subtree whose sum of values of nodes is zero.

After doing so, return the number of nodes remaining in the tree.

Example 1:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

Constraints:

1 <= nodes <= 10^4
-10^5 <= value[i] <= 10^5
parent.length == nodes
parent[0] == -1 which indicates that 0 is the root.

Solution: Inorder Traversal

For each node, return the sum of all its subtrees and number of nodes including itself after removal.

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

C++

// Author: Huahua

class Solution {

public:

int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {

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

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

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

// Returns <sum, nodes> of subtree n.

function<pair<int,int>(int)> traverse = [&](int n) {

int sum = value[n];

int count = 1;

for (int x : g[n]) {

auto [s, c] = traverse(x);

sum += s;

count += s ? c : 0;

}

return make_pair(sum, sum ? count : 0);

};

return traverse(0).second;

}

};

花花酱 LeetCode 1261. Find Elements in a Contaminated Binary Tree

By zxi on November 26, 2019

Given a binary tree with the following rules:

root.val == 0
If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2

Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.

You need to first recover the binary tree and then implement the FindElements class:

FindElements(TreeNode* root) Initializes the object with a contamined binary tree, you need to recover it first.
bool find(int target) Return if the target value exists in the recovered binary tree.

Example 1:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output

[null,false,true]

Explanation FindElements findElements = new FindElements([-1,null,-1]); findElements.find(1); // return False findElements.find(2); // return True

Example 2:

Input
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
Output

[null,true,true,false]

Explanation FindElements findElements = new FindElements([-1,-1,-1,-1,-1]); findElements.find(1); // return True findElements.find(3); // return True findElements.find(5); // return False

Example 3:

Input
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
Output

[null,true,false,false,true]

Explanation FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]); findElements.find(2); // return True findElements.find(3); // return False findElements.find(4); // return False findElements.find(5); // return True

Constraints:

TreeNode.val == -1
The height of the binary tree is less than or equal to 20
The total number of nodes is between [1, 10^4]
Total calls of find() is between [1, 10^4]
0 <= target <= 10^6

Solutoin 1: Recursion and HashSet

Time complexity: Recover O(n), find O(1)
Space complexity: O(n)

C++

// Author: Huahua

class FindElements {

public:

FindElements(TreeNode* root) {

recover(root, 0);

}

bool find(int target) {

return s_.count(target);

}

private:

unordered_set<int> s_;

void recover(TreeNode* root, int val) {

if (!root) return;

root->val = val;

s_.insert(val);

recover(root->left, val * 2 + 1);

recover(root->right, val * 2 + 2);

}

};

Solution 2: Recursion and Binary format

The binary format of t = (target + 1) (from high bit to low bit, e.g. in reverse order) decides where to go at each node.
t % 2 == 1, go right, otherwise go left
t = t / 2 or t >>= 1

e.g. target = 13, t = 13 + 1 = 14

t = 14, t % 1 = 0, t / 2 = 7, left

t = 7, t % 1 = 1, t / 2 = 3, right

t = 3, t % 1 = 1, t / 2 = 1, right

13 => right, right, left

Time complexity: Recover O(n), find O(log|target|)
Space complexity: O(1)

C++

// Author: Huahua

class FindElements {

public:

FindElements(TreeNode* root): root_(root) {

recover(root, 0);

}

bool find(int target) {

++target;

stack<bool> right;

while (target != 1) {

right.push(target & 1);

target >>= 1;

}

TreeNode* node = root_;

while (!right.empty() && node) {

node = right.top() ? node->right : node->left;

right.pop();

}

return node;

}

private:

TreeNode* root_;

void recover(TreeNode* root, int val) {

if (!root) return;

root->val = val;

recover(root->left, val * 2 + 1);

recover(root->right, val * 2 + 2);

}

};

花花酱 LeetCode 129. Sum Root to Leaf Numbers

By zxi on October 9, 2019

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

int sumNumbers(TreeNode* root) {

int ans = 0;

function<void(TreeNode*, int)> traverse = [&](TreeNode* t, int num) {

if (!t) return;

num = num * 10 + t->val;

if (t->left || t->right) {

traverse(t->left, num);

traverse(t->right, num);

} else {

ans += num;

}

};

traverse(root, 0);

return ans;

}

};