Posts published in “Tree”

花花酱 LeetCode 823. Binary Trees With Factors

By zxi on April 29, 2018

Problem

题目大意：给你一些可以重复使用的数字问能够构成多少种不同的特殊二叉树（根结点的值需为子节点值的乘积）。

https://leetcode.com/problems/binary-trees-with-factors/description/

Given an array of unique integers, each integer is strictly greater than 1.

We make a binary tree using these integers and each number may be used for any number of times.

Each non-leaf node’s value should be equal to the product of the values of it’s children.

How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.

Example 1:

Input: A = [2, 4]
Output: 3 Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

Note:

1 <= A.length <= 1000.
2 <= A[i] <= 10 ^ 9.

Solution: DP

Use dp[i] to denote the number of valid binary trees using the first i + 1 smallest elements and roots at A[i].

dp[i] = sum(dp[j] * dp[i/j]), 0 <= j < i, A[i] is a factor of A[j] and A[i] / A[j] also in A.

      A[i]
     /    \
 A[j]  (A[i]/A[j])
  / \     / \
 .....   .....

ans = sum(dp[i]), for all possible i.

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 53 ms

class Solution {

public:

int numFactoredBinaryTrees(vector<int>& A) {

constexpr long kMod = 1000000007;

std::sort(A.begin(), A.end());

unordered_map<int, long> dp;

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

dp[A[i]] = 1;

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

if (A[i] % A[j] == 0 && dp.count(A[i] / A[j]))

dp[A[i]] += (dp[A[j]] * dp[A[i] / A[j]]) % kMod;

}

long ans = 0;

for (const auto& kv : dp)

ans += kv.second;

return ans % kMod;

}

};

花花酱 LeetCode 331. Verify Preorder Serialization of a Binary Tree

By zxi on April 13, 2018

Problem

题目大意：验证二叉树前序遍历的序列化是否合法。

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/description/

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where #represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing nullpointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution: Recursion

If a node is not null, it must has two children, thus verify left subtree and right subtree recursively.
If a not is null, the current char must be ‘#’

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

bool isValidSerialization(string preorder) {

int pos = 0;

return isValid(preorder, pos) && pos == preorder.length();

}

private:

bool isValid(const string& s, int& pos) {

if (pos >= s.length()) return false;

if (isdigit(s[pos])) {

while (isdigit(s[pos])) ++pos;

return isValid(s, ++pos) && isValid(s, ++pos);

}

return s[pos++] == '#';

}

};

花花酱 LeetCode 814. Binary Tree Pruning

By zxi on April 7, 2018

Problem:

题目大意：把不含有1的节点的子树全部删除。

https://leetcode.com/problems/binary-tree-pruning/description/

We are given the head node root of a binary tree, where additionally every node’s value is either a 0 or a 1.

Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)

Example 1:
Input: [1,null,0,0,1]
Output: [1,null,0,null,1]
 
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Example 2:
Input: [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

Example 3:
Input: [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]

Note:

The binary tree will have at most 100 nodes.
The value of each node will only be 0 or 1.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

TreeNode* pruneTree(TreeNode* root) {

if (!root) return root;

root->left = pruneTree(root->left);

root->right = pruneTree(root->right);

if (root->val == 1 || root->left || root->right)

return root;

delete root;

return nullptr;

}

};

Java

// Author: Huahua

// Running time: 2 ms

class Solution {

public TreeNode pruneTree(TreeNode root) {

if (root == null) return root;

root.left = pruneTree(root.left);

root.right = pruneTree(root.right);

return (root.val == 1 || root.left != null || root.right != null) ? root : null;

}

Python3

// Author: Huahua

// Running time: 36 ms

class Solution:

def pruneTree(self, root):

if not root: return root

root.left = self.pruneTree(root.left)

root.right = self.pruneTree(root.right)

return root if root.val == 1 or root.left or root.right else None

花花酱 LeetCode 450. Delete Node in a BST

By zxi on March 24, 2018

Problem

https://leetcode.com/problems/delete-node-in-a-bst/description/

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

Solution: Recursion

Time complexity: O(h)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 36 ms

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

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

* };

class Solution {

public:

TreeNode* deleteNode(TreeNode* root, int key) {

if (root == nullptr) return root;

if (key > root->val) {

root->right = deleteNode(root->right, key);

} else if (key < root->val) {

root->left = deleteNode(root->left, key);

} else {

TreeNode* new_root = nullptr;

if (root->left == nullptr) {

new_root = root->right;

} else if (root->right == nullptr) {

new_root = root->left;

} else {

// Find the min node in the right sub tree

TreeNode* parent = root;

new_root = root->right;

while (new_root->left != nullptr) {

parent = new_root;

new_root = new_root->left;

}

if (parent != root) {

parent->left = new_root->right;

new_root->right = root->right;

}

new_root->left = root->left;

}

delete root;

return new_root;

}

return root;

}

};

// Author: Huahua

// Running time: 35 ms

class Solution {

public:

TreeNode* deleteNode(TreeNode* root, int key) {

if (root == nullptr) return root;

if (key > root->val) {

root->right = deleteNode(root->right, key);

} else if (key < root->val) {

root->left = deleteNode(root->left, key);

} else {

if (root->left != nullptr && root->right != nullptr) {

TreeNode* min = root->right;

while (min->left != nullptr) min = min->left;

root->val = min->val;

root->right = deleteNode(root->right, min->val);

} else {

TreeNode* new_root = root->left == nullptr ? root->right : root->left;

root->left = root->right = nullptr;

delete root;

return new_root;

}

return root;

}

};

花花酱 LeetCode 437. Path Sum III

By zxi on March 24, 2018

Problem

题目大意：给你一棵二叉树，返回单向的路径和等于sum的路径数量。

https://leetcode.com/problems/path-sum-iii/description/

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Solution 1: Recursion

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 21 ms

class Solution {

public:

int pathSum(TreeNode* root, int sum) {

if (!root) return 0;

return numberOfPaths(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);

}

private:

int numberOfPaths(TreeNode* root, int left) {

if (!root) return 0;

left -= root->val;

return (left == 0 ? 1 : 0) + numberOfPaths(root->left, left) + numberOfPaths(root->right, left);

}

};

Solution 2: Running Prefix Sum

Same idea to 花花酱 LeetCode 560. Subarray Sum Equals K

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 13 ms (beats 97.74%)

public:

int pathSum(TreeNode* root, int sum) {

ans_ = 0;

sums_ = {{0, 1}};

pathSum(root, 0, sum);

return ans_;

}

private:

int ans_;

unordered_map<int, int> sums_;

void pathSum(TreeNode* root, int cur, int sum) {

if (!root) return;

cur += root->val;

ans_ += sums_[cur - sum];

++sums_[cur];

pathSum(root->left, cur, sum);

pathSum(root->right, cur, sum);

--sums_[cur];

}

};

Posts published in “Tree”

花花酱 LeetCode 823. Binary Trees With Factors

Problem

Solution: DP

花花酱 LeetCode 331. Verify Preorder Serialization of a Binary Tree

Problem

Solution: Recursion

花花酱 LeetCode 814. Binary Tree Pruning

Problem:

Solution: Recursion

花花酱 LeetCode 450. Delete Node in a BST

Problem

Solution: Recursion

花花酱 LeetCode 437. Path Sum III

Problem

Example:

Solution 1: Recursion

Solution 2: Running Prefix Sum

Related Problem