Tree
98. Validate Binary Search Tree
class Solution {
public:
bool isValidBST(TreeNode* root) {
TreeNode *min_node = nullptr, *max_node = nullptr;
return isInRange(root, min_node, max_node);
}
bool isInRange(TreeNode* root, TreeNode* min_node, TreeNode* max_node) {
if (!root) return true;
if ((min_node && min_node->val >= root->val) || (max_node && max_node->val <= root->val))
return false;
return isInRange(root->left, min_node, root) && isInRange(root->right, root, max_node);
}
};
99. Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode* pre = nullptr, *first = nullptr, *second = nullptr;
findReverse(root, first, second, pre);
if (first && second) swap(first->val, second->val);
}
void findReverse(TreeNode* root, TreeNode*& first, TreeNode*& second, TreeNode*& pre) {
if (!root) return;
findReverse(root->left, first, second, pre);
if (pre) {
if (pre->val >= root->val) {
if (!first) first = pre;
second = root;
}
}
pre = root;
findReverse(root->right, first, second, pre);
}
};
105. Construct Binary Tree from Preorder and Inorder Traversal
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int pre_idx = 0;
if (!preorder.size()) return nullptr;
return build(preorder, inorder, pre_idx, 0, inorder.size() - 1);
}
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int& pre_idx, int start, int end) {
if (start > end) return nullptr;
TreeNode* node = new TreeNode(preorder[pre_idx++]);
if (start == end) return node;
int index = start;
for (int i = start; i <= end; ++i) {
if (node->val == inorder[i]) {
index = i;
break;
}
}
node->left = build(preorder, inorder, pre_idx, start, index - 1);
node->right = build(preorder, inorder, pre_idx, index+1, end);
return node;
}
};
199. Binary Tree Right Side View
Given 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.
For example: Given the following binary tree, 1 <--- / \ 2 3 <--- \ \ 5 4 <--- You should return [1, 3, 4].
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if (!root) return res;
dfs(root, res, 1);
return res;
}
void dfs(TreeNode* root, vector<int>& res, int level) {
if (!root) return;
if (res.size() < level) res.push_back(root->val);
dfs(root->right, res, level + 1);
dfs(root->left, res, level + 1);
}
};
230. Kth Smallest Element in a BST
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note: You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
/**
* 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:
int kthSmallest(TreeNode* root, int k) {
// stack<TreeNode*> st;
// int ret = -1;
// if (!root) return ret;
// while (root) {
// st.push(root);
// root = root->left;
// }
// while (!st.empty()) {
// auto node = st.top();
// st.pop();
// if (--k == 0) {
// ret = node->val;
// break;
// }
// node = node->right;
// while (node) {
// st.push(node);
// node = node->left;
// }
// }
// return ret;
if (!root) return -1;
int count = getCount(root->left);
if (k == count + 1) return root->val;
else if ( k < count + 1) return kthSmallest(root->left, k);
else {
return kthSmallest(root->right, k - count - 1);
}
}
int getCount(TreeNode* node) {
if (!node) return 0;
return 1 + getCount(node->left) + getCount(node->right);
}
};
236. Lowest Common Ancestor of a Binary Tree
/**
* 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return root;
if (root == p || root == q) return root;
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if(left && right) return root;
return left ? left : right;
}
};
250 Count Univalue Subtrees
Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.
For example: Given binary tree,
5 / \ 1 5 / \ \ 5 5 5return 4.
class Solution {
public:
int countUnivalSubtrees(TreeNode* root) {
int res = 0;
countUni(root, res);
return res;
}
bool countUni(TreeNode* root, int& res) {
if (!root) return true;
bool left = countUni(root->left, res);
bool right = countUni(root->right, res);
if (left && right && (!root->left || root->left->val == root->val)
&& (!root->right || root->right->val == root->val)) {
res += 1;
return true;
}
return false;
}
};
255 Verify Preorder Sequence in Binary Search Tree
Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.
You may assume each number in the sequence is unique.
Follow up: Could you do it using only constant space complexity?
class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
size_t len = preorder.size();
if (!len) return true;
stack<int> st;
int cur_min = INT_MIN;
for (auto node : preorder) {
if (node < cur_min) return false;
while (!st.empty() && st.top() < node) {
cur_min = st.top();
st.pop();
}
st.push(node);
}
return true;
}
};
272 Closest Binary Search Tree Value II
Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Note: Given target value is a floating point. You may assume k is always valid, that is: k ≤ total nodes. You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Follow up: Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
Hint: Consider implement these two helper functions: getPredecessor(N), which returns the next smaller node to N. getSuccessor(N), which returns the next larger node to N. Try to assume that each node has a parent pointer, it makes the problem much easier. Without parent pointer we just need to keep track of the path from the root to the current node using a stack. You would need two stacks to track the path in finding predecessor and successor node separately.
class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<int> res;
stack<TreeNode*> lower;
stack<TreeNode*> upper;
TreeNode* cur = root;
while (cur) {
if (static_cast<double>(cur->val) > target) {
upper.push(cur);
cur = cur->left;
} else {
lower.push(cur);
cur = cur->right;
}
}
while (res.size() != k) {
if (lower.empty()) {
// get largest k;
auto top = getSuccessor(upper);
if (top) res.push_back(top->val);
} else if (upper.empty()) {
auto top = getPredecessor(lower);
if (top) res.push_back(top->val);
} else {
int l = lower.top()->val;
int r = upper.top()->val;
if (fabs(static_cast<double>(l) - target) < fabs(static_cast<double>(r) - target)) {
res.push_back(l);
getPredecessor(lower);
} else {
res.push_back(r);
getSuccessor(upper);
}
}
}
return res;
}
TreeNode* getPredecessor(stack<TreeNode*>& pre) {
if (!pre.size()) return nullptr;
auto cur = pre.top();
auto ret = cur;
pre.pop();
cur = cur->left;
while (cur) {
pre.push(cur);
cur = cur->right;
}
return ret;
}
TreeNode* getSuccessor(stack<TreeNode*>& suc) {
if (!suc.size()) return nullptr;
auto cur = suc.top();
auto ret = cur;
suc.pop();
cur = cur->right;
while (cur) {
// cout << "push: " << cur->val << endl;
suc.push(cur);
cur=cur->left;
}
return ret;
}
};
285 Inorder Successor in BST
O(N)
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
find_sucessor(root, p);
return successor;
}
void find_sucessor(TreeNode* node, TreeNode* p) {
if (!node) return;
find_sucessor(node->left, p);
if (pre == p) {
successor = node;
// return;
}
pre = node;
find_sucessor(node->right, p);
}
private:
TreeNode* pre = nullptr;
TreeNode* successor = nullptr;
};
O(logN) recursive version
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
if (!root || !p) return root;
if (root->val <= p->val) return inorderSuccessor(root->right, p);
auto left = inorderSuccessor(root->left, p);
return left ? left : root;
}
};
O(logN) Iterative version
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
if (!root || !p) return root;
TreeNode* res = nullptr;
while (root) {
if (root->val > p->val) {
res = root;
root = root->left;
} else {
root = root->right;
}
}
return res;
}
};
297. Serialize and Deserialize Binary Tree
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
ostringstream os;
serialize(root, os);
return os.str();
}
void serialize(TreeNode* root, ostringstream& os) {
if (!root) {
os << "#" << ",";
return;
}
os << root->val << ",";
serialize(root->left, os);
serialize(root->right, os);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
istringstream is(data);
return deserialize(is);
}
TreeNode* deserialize(istringstream& is) {
if (is.eof()) return nullptr;
string val;
getline(is, val, ',');
if (val == "#") return nullptr;
TreeNode* node = new TreeNode(stoi(val));
node->left = deserialize(is);
node->right = deserialize(is);
return node;
}
};
298 Binary Tree Longest Consecutive Sequence
Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).
For example,
1 \ 3 / \ 2 4 \ 5Longest consecutive sequence path is 3-4-5, so return 3.
2 \ 3 / 2 / 1Longest consecutive sequence path is 2-3,not3-2-1, so return 2.
class Solution {
public:
int longestConsecutive(TreeNode* root) {
int res = 0;
if (!root) return res;
longestConsecutive(root, 1, res);
return res;
}
void longestConsecutive(TreeNode* root, int cur, int& res) {
if (cur > res) res = cur;
if (root->left) {
int next = root->left->val == root->val + 1 ? cur + 1 : 1;
longestConsecutive(root->left, next, res);
}
if (root->right) {
int next = root->right->val == root->val + 1 ? cur + 1 : 1;
longestConsecutive(root->right, next, res);
}
}
};
314 Binary Tree Vertical Order Traversal
Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Examples:
Given binary tree [3,9,20,null,null,15,7],
3 /\ / \ 9 20 /\ / \ 15 7return its vertical order traversal as:
[ [9], [3,15], [20], [7] ]Given binary tree [3,9,8,4,0,1,7],
3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7return its vertical order traversal as:
[ [4], [9], [3,0,1], [8], [7] ]Given binary tree [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5),
3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 /\ / \ 5 2return its vertical order traversal as:
[ [4], [9,5], [3,0,1], [8,2], [7] ]
class Solution {
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
map<int, vector<int>> level;
vector<vector<int>> res;
if (!root) return res;
queue<pair<TreeNode*, int>> q;
q.push({root, 0});
while (!q.empty()) {
auto cur = q.front(); q.pop();
level[cur.second].push_back(cur.first->val);
if (cur.first->left) q.push({cur.first->left, cur.second-1});
if (cur.first->right) q.push({cur.first->right, cur.second+1});
}
for (auto kv : level) {
res.push_back(kv.second);
}
return res;
}
};
without hash table:
class Solution {
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
std::queue<pair<int, TreeNode*>> q;
vector<vector<int>> left;
vector<vector<int>> right;
vector<int> mid;
if(!root) return left;
q.push({0,root});
while(!q.empty()){
auto p = q.front();
q.pop();
if(p.first == 0) mid.push_back(p.second->val);
else if(p.first > 0){
if(p.first > right.size()) right.push_back(vector<int>());
right[p.first-1].push_back(p.second->val);
}
else{
if(0-p.first > left.size()) left.push_back(vector<int>());
left[-1-p.first].push_back(p.second->val);
}
if(p.second->left) q.push({p.first-1, p.second->left});
if(p.second->right) q.push({p.first+1, p.second->right});
}
int r = right.size();
reverse(left.begin(), left.end());
left.push_back(mid);
for(int i=0; i<r; i++) left.push_back(right[i]);
return left;
}
};
331. Verify Preorder Serialization of a Binary Tree
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 null pointer.
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
class Solution {
public:
bool isValidSerialization(string preorder) {
istringstream iss(preorder);
return isValid(iss) && iss.eof();
}
bool isValid(istringstream& iss) {
string node;
if (!iss || !getline(iss, node, ',')) return false;
if (node == "#") return true;
return isValid(iss) && isValid(iss);
}
};
[Valid Postorder Traversal of BST]
Given a integer array, please determine if it is a postorder traversal result of an arbitrary Binary Search Tree.
For example:{5,7,6,9,11,10,8} is valid {7,4,6,5} is not valid
bool valid_bst_post(int arr[], int n) {
if(!arr || n <= 0) return false;
int root = arr[n - 1];
int left = 0;
for(; left < n - 1; ++left) {
if(arr[left] > root) break;
}
for(int right = left; right < n - 1; ++right) {
if(arr[right] < root) return false;
}
bool l_valid = true, r_valid = true;
if (left > 0) l_valid = valid_bst_post(arr, left);
if (left < n - 1) r_valid = valid_bst_post(arr + left, n - left - 1);
return l_valid && r_valid;
}