513.找树左下角的值
用最笨的迭代法做出来了。
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
int last_value;
que.push(root);
while(!que.empty()){
int pre_size = que.size();
for(int i=0; i<pre_size; i++){
TreeNode* temp_node = que.front();
last_value = temp_node->val;
if((temp_node->right!=nullptr)){
que.push(temp_node->right);
}
if(temp_node->left!=nullptr){
que.push(temp_node->left);
}
que.pop();
}
}
return last_value;
}
};
吃完饭后，又觉得还是试一下写递归吧。上午的时候简单看了下怎么写，现在改了改也会写了。
class Solution {
public:
int result;
int max_dep = 0;
void travesal(TreeNode* cur,int cur_dep){
if((cur->left == nullptr) && (cur->right == nullptr)){
if(max_dep < cur_dep){
max_dep = cur_dep;
result = cur->val;
}
}
if(cur->left != nullptr){
cur_dep++;
travesal(cur->left,cur_dep);
cur_dep--;
}
if(cur->right != nullptr){
cur_dep++;
travesal(cur->right,cur_dep);
cur_dep--;
}
}
int findBottomLeftValue(TreeNode* root) {
travesal(root,1);
return result;
}
};
112. 路径总和 113.路径总和ii
虽然方法笨，但还是写出来了一种解法。写这个其实也是遇到很多问题。
首先，我先写的是travesal(TreeNode* cur,int sum)，然后再遇到cur==nullptr的时候再对比sum和targetsum是不是相等的，我先是错误的把targetsum的值直接传到了sum里，所以sum的值从一开始就加的不对。
发现了这个问题并解决了之后，遇到了function无法分清是不是叶节点的问题。我之前的travesal里面其实没有判断是不是叶节点，而只是看是不是为null的子节点。要看是不是叶节点，就要判断该节点是不是左右孩子都为null。
这道题有不少容易错的地方。还需要多练这道题。
class Solution {
public:
vector<vector<int>> all_list;
void travesal(TreeNode* cur, vector<int> vt){
if((cur->left == nullptr) && (cur->right == nullptr)){
vt.push_back(cur->val);
all_list.push_back(vt);
return ;
}
vt.push_back(cur->val);
if(cur->left != nullptr){
travesal(cur->left, vt);
}
if(cur->right != nullptr){
travesal(cur->right, vt);
}
}
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == nullptr)
return false;
if((root->left == nullptr) && (root->right == nullptr) && (root->val == targetSum))
return true;
vector<int> list;
travesal(root,list);
for(int i=0; i<all_list.size(); i++){
int sum = 0;
for(int j=0; j<all_list[i].size();j++){
sum = sum+ all_list[i][j];
}
if((sum == targetSum) && (all_list[i].size()>1)){
return true;
}
}
return false;
}
};
随后的路径总和ii，我就是简单修改了一下。
class Solution {
public:
vector<vector<int>> all_list;
void travesal(TreeNode* cur, vector<int> vt){
if((cur->left == nullptr) && (cur->right == nullptr)){
vt.push_back(cur->val);
all_list.push_back(vt);
return ;
}
vt.push_back(cur->val);
if(cur->left != nullptr){
travesal(cur->left, vt);
}
if(cur->right != nullptr){
travesal(cur->right, vt);
}
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> res_list;
if(root == nullptr)
return res_list;
if((root->left == nullptr) && (root->right == nullptr) && (root->val == targetSum)){
vector<int> list;
list.push_back(root->val);
res_list.push_back(list);
}
vector<int> list;
travesal(root,list);
for(int i=0; i<all_list.size(); i++){
int sum = 0;
for(int j=0; j<all_list[i].size();j++){
sum = sum+ all_list[i][j];
}
if((sum == targetSum) && (all_list[i].size()>1)){
res_list.push_back(all_list[i]);
}
}
return res_list;
}
};
106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
懒得写了，但是我想的也是这个意思。唯一没想明白的就是怎么递归，原来是写两个，一个是左边，一个是右边。而且到时候call递归的之前，要把inorder和postorder的vetor段都分好，然后再call。call的时候inorder的左边配postorder的左边，inorder的右边配postorder的右边。
class Solution {
public:
TreeNode* travelTree(vector<int>& inorder, vector<int>& postorder){
if (postorder.size() == 0) return NULL;
// 后序遍历数组最后一个元素，就是当前的中间节点
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
// 叶子节点
if (postorder.size() == 1) return root;
// 找到中序遍历的切割点
int index;
for (index = 0; index < inorder.size(); index++) {
if (inorder[index] == rootValue) break;
}
vector<int> inorder_left(inorder.begin(),inorder.begin()+index);
vector<int> inorder_right(inorder.begin()+index+1,inorder.end());
postorder.resize(postorder.size()-1);
vector<int> postorder_left(postorder.begin(),postorder.begin()+inorder_left.size());
vector<int> postorder_right(postorder.begin()+inorder_left.size(),postorder.end());
root->left = travelTree(inorder_left,postorder_left);
root->right= travelTree(inorder_right,postorder_right);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if((inorder.size() == 0) || (postorder.size() == 0))
return nullptr;
return travelTree(inorder,postorder);
}
};
