文章目录
problem Ⅰ
199. Binary Tree Right Side View
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: []
solution 1 BFS
/**
* 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 Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if(!root)return res;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
int n = que.size();
for(; n>0; n--){
TreeNode* node = que.front();
que.pop();
if(n==1)res.push_back(node->val);
if(node->left)que.push(node->left);
if(node->right)que.push(node->right);
}
}
return res;
}
};
solution 2 DFS
/**
* 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 Solution {
public:
vector<int> res;
void dfs_(TreeNode* root, int depth){
if(!root)return;
if(depth == res.size())
res.push_back(root->val);
dfs_(root->right, depth+1);
dfs_(root->left, depth+1);
}
vector<int> rightSideView(TreeNode* root) {
dfs_(root, 0);
return res;
}
};
NOTE:
we can observe that the solution using DFS with some trick is extrmely faster than BFS
problem 2
113. Path Sum II
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: []
Example 3:
Input: root = [1,2], targetSum = 0
Output: []
solution DFS
/**
* 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 Solution {
public:
vector<vector<int>> res;
vector<int> tmp;
int target;
void dfs_(TreeNode* root, int cumsum){
cumsum+=root->val;
tmp.push_back(root->val);
if(cumsum == target && !root->left && !root->right)
res.push_back(tmp);
if(root->left)
dfs_(root->left, cumsum);
if(root->right)
dfs_(root->right, cumsum);
cumsum -= root->val;
tmp.pop_back();
return;
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
target = targetSum;
if(!root)return res;
dfs_(root, 0);
return res;
}
};
problem 3
450. Delete Node in a BST
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.
Example 1:
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: 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 above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted
Example 2:
Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.
Example 3:
Input: root = [], key = 0
Output: []
solution 1
/**
* 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 Solution {
public:
TreeNode* findMin(TreeNode* root){
TreeNode* pre = root->left;
while(pre->left && pre->left->left)
pre = pre->left;
if(!pre->left){
root->left = pre->right;
return pre;
}else{
TreeNode* mins = pre->left;
pre->left = mins->right;
return mins;
}
}
TreeNode* deleteNode(TreeNode* root, int key) {
if(root){
if(root->val < key)
root->right = deleteNode(root->right, key);
else if(root->val > key)
root->left = deleteNode(root->left, key);
else{
if(!root->right)return root->left;
if(!root->right->left){
root->right->left = root->left;
return root->right;
}
TreeNode* mins = findMin(root->right);
mins->left = root->left;
mins->right = root->right;
return mins;
}
}
return root;
}
};
solution 2 recursive [a little bit slow]
/**
* 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 Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root){
if(key < root->val) root->left = deleteNode(root->left, key);
else if(key > root->val) root->right = deleteNode(root->right, key);
else{
if(!root->left && !root->right) return NULL;
if (!root->left || !root->right)
return root->left ? root->left : root->right;
TreeNode* temp = root->left;
while(temp->right != NULL) temp = temp->right;
root->val = temp->val;
root->left = deleteNode(root->left, temp->val);
}
}
return root;
}
};