[leetcode] 树（Ⅱ）
All questions are simple level.
Construct String from Binary Tree
Question[606]：You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way. The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.
Example
Input: Binary tree: [1,2,3,4]
1
/ \
2 3
/
4
Output: "1(2(4))(3)"
Explanation: Originallay it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)".
Solution
Use pre-order traversal. These two methods is the same. The first one is implemented by passing arguments by reference. The second one is implemented by returned value.
class Solution
{
public:
string tree2str(TreeNode *t)
{
// string s = "";
// preorder(t, s);
// return s;
return preorder2(t);
}
void preorder(TreeNode *p, string &s)
{
if (p == nullptr)
return;
string sval = to_string(p->val);
string l, r;
preorder(p->left, l);
preorder(p->right, r);
s += sval;
bool lflag = (l != "");
bool rflag = (r != "");
if (lflag && rflag)
s += "(" + l + ")(" + r + ")";
if (!lflag && rflag)
s += "()(" + r + ")";
if (lflag && !rflag)
s += "(" + l + ")";
}
string preorder2(TreeNode *p)
{
if (p == nullptr)
return "";
bool l = (p->left != nullptr);
bool r = (p->right != nullptr);
string sval = to_string(p->val);
if (l && r)
return sval + "(" + preorder2(p->left) + ")(" + preorder2(p->right) + ")";
if (!l && r)
return sval + "()(" + preorder2(p->right) + ")";
if (l && !r)
return sval + "(" + preorder2(p->left) + ")";
return sval;
}
};
Merge Two Binary Trees
Question[617]: Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Solution: Two versions, including recursion and iteration.
-
Recursion version-1: create a completely new tree
class Solution { public: TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2) { TreeNode *root = nullptr; innerMerge(root, t1, t2); return root; } void innerMerge(TreeNode *&p, TreeNode *t1, TreeNode *t2) { bool flag1 = (t1 != nullptr); bool flag2 = (t2 != nullptr); if (flag1 && flag2) p = new TreeNode(t1->val + t2->val); else if (!flag1 && flag2) p = new TreeNode(t2->val); else if (flag1 && !flag2) p = new TreeNode(t1->val); else return; innerMerge(p->left, flag1 ? t1->left : nullptr, flag2 ? t2->left : nullptr); innerMerge(p->right, flag1 ? t1->right : nullptr, flag2 ? t2->right : nullptr); } }; -
Recursion version-2: directly modify on
t1class Solution { public: TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2) { return innerMerge(t1, t2); } TreeNode *innerMerge(TreeNode *t1, TreeNode *t2) { if (t1 == nullptr) return t2; if (t2 == nullptr) return t1; t1->val += t2->val; t1->left = innerMerge(t1->left, t2->left); t1->right = innerMerge(t1->right, t2->right); return t1; } }; -
Iteration-version implemented by pre-order traversal, modify on
t1:TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2) { return preorderMerge(t1, t2); } TreeNode *preorderMerge(TreeNode *t1, TreeNode *t2) { typedef pair<TreeNode *, TreeNode *> node; if (t1 == nullptr) return t2; stack<node> s; s.push(node(t1, t2)); while (!s.empty()) { node n = s.top(); s.pop(); if (n.second == nullptr) continue; n.first->val += n.second->val; if (n.first->left == nullptr) n.first->left = n.second->left; else s.push(node(n.first->left, n.second->left)); if (n.first->right == nullptr) n.first->right = n.second->right; else s.push(node(n.first->right, n.second->right)); } return t1; }
Average of Levels in Binary Tree
Question[637]: Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example
Input:
3
/ \
9 20
/ \
15 7
Output: [3, 14.5, 11]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Solution
-
Level-order traversal. Use the map
sumrecordto record the sum of each level. Usenumrecordto record the number of nodes of each level.vector<double> averageOfLevels(TreeNode *root) { typedef pair<TreeNode *, int> node; unordered_map<int, double> sumrecord; unordered_map<int, int> numrecord; queue<node> q; q.push(node(root, 0)); while (!q.empty()) { auto n = q.front(); q.pop(); sumrecord[n.second] += n.first->val; numrecord[n.second]++; if (n.first->left != nullptr) q.push(node(n.first->left, n.second + 1)); if (n.first->right != nullptr) q.push(node(n.first->right, n.second + 1)); } vector<double> v(numrecord.size()); for (auto &x : sumrecord) v[x.first] = x.second / numrecord[x.first]; return v; } -
Level-order traversal. Only use queue, discard the help of
nodeandunordered_map.vector<double> levelorder(TreeNode *root) { vector<double> v; queue<TreeNode *> q; q.push(root); while (!q.empty()) { queue<TreeNode *> nextlevel; int64_t sum = 0; int counter = 0; while (!q.empty()) { auto p = q.front(); q.pop(); sum += p->val, counter++; if (p->left != nullptr) nextlevel.push(p->left); if (p->right != nullptr) nextlevel.push(p->right); } q = nextlevel; v.push_back(sum * 1.0 / counter); } return v; }
Two Sum IV – Input is a BST
Question[653]: Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
Output: True
Explanation: 9 = 3+6, 9 = 2+7, 9 = 4+5
Solution
First, implement a function named search(root, val) which is used to search val in a tree root. Then, traversal the tree root to judge every node p whether there is another node q satisfies p->val + q->val == k.
bool search(TreeNode *p, int val, TreeNode *exceptNode)
{
if (p == nullptr)
return false;
if (p->val == val && p != exceptNode)
return true;
if (val < p->val)
return search(p->left, val, exceptNode);
return search(p->right, val, exceptNode);
}
bool levelorder(TreeNode *root, int k)
{
queue<TreeNode *> q;
q.push(root);
while (!q.empty())
{
auto p = q.front();
q.pop();
int val = k - p->val;
if (search(root, val, p))
return true;
if (p->left != nullptr)
q.push(p->left);
if (p->right != nullptr)
q.push(p->right);
}
return false;
}
Trim a Binary Search Tree
Question[669]: Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example-1
Input-1:
1
/ \
0 2
L = 1
R = 2
Output-1:
1
\
2
Example-2
Input-2:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
Output-2:
3
/
2
/
1
Solution
Assume L=8 and R=16 here. For each node of a BST, there are only three cases:
- val < L
- val > R
- L <= val <= R
When val < L, for an example:
parent parent parent
| | |
9 ==> 9 ==> right
/ \ / \
left right null right
All values in the left sub-tree should be less than 9, hence the left sub-tree should be discarded. And because of ‘9’ is less than L, hence it also should be discarded. The code to do these two operations is:
p->left = nullptr, p = trim(p->right)
The case val > R is similar to case val < L.
For the case L <= val <= R, there is nothing to do on the val node. Just continue to trim on its left sub-tree and right sub-tree.
Version-1:
TreeNode *trimBST(TreeNode *root, int L, int R)
{
return innerTrim(root, L, R);
}
TreeNode *innerTrim(TreeNode *&p, int l, int r)
{
if (p == nullptr)
return nullptr;
if (p->val < l)
{
p->left = nullptr;
return p = innerTrim(p->right, l, r);
}
else if (p->val > r)
{
p->right = nullptr;
return p = innerTrim(p->left, l, r);
}
else
{
p->left = innerTrim(p->left, l, r);
p->right = innerTrim(p->right, l, r);
return p;
}
}
Version-2:
TreeNode *trimBST(TreeNode *root, int L, int R)
{
innerTrim2(root, L, R);
return root;
}
void innerTrim2(TreeNode *&p, int l, int r)
{
if (p == nullptr)
return;
if (p->val < l)
{
p->left = nullptr, p = p->right;
innerTrim2(p, l, r);
return;
}
else if (p->val > r)
{
p->right = nullptr, p = p->left;
innerTrim2(p, l, r);
return;
}
else
{
innerTrim2(p->left, l, r);
innerTrim2(p->right, l, r);
}
}
Second Minimum Node In a Binary Tree
Question[671]: Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds. Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree. If no such second minimum value exists, output -1 instead.
Example-1
Input:
2
/ \
2 5
/ \
5 7
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
Solution
The smallest value in the tree is root->val (at level-0) . Hence the solution is to find the smallest value in all numbers greater (at level >= 1) than root->val.
class Solution
{
public:
int findSecondMinimumValue(TreeNode *root)
{
if (root == nullptr || root->left == nullptr)
return -1;
int minval = root->val;
int result = -1;
queue<TreeNode *> q;
auto p = root;
q.push(p);
while (!q.empty())
{
p = q.front();
q.pop();
if (p->val > minval)
result = result == -1 ? p->val : min(result, p->val);
if (p->left)
q.push(p->left);
if (p->right)
q.push(p->right);
}
return result;
}
};
Longest Univalue Path
Question[687]: Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root. The length of path between two nodes is represented by the number of edges between them.
Example
Input:
1
/ \
4 5
/ \ \
4 4 5
Output: 2
Solution
NOT PASS YET.