代码随想录算法训练营第36期DAY21

DAY21

自己写的，过了（注意到层序遍历中，que队头存的是最左边的节点，再写一个getheight函数控制最大高度就好）。待会看解析，掌握迭代、递归。

优化迭代法：不用找最大深度，直接记录每层的res，用i=0记录。While结束前的那层，就是最后一层。

/**
* 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:
int geth(TreeNode* root)
{
if(root==nullptr) return 0;
return 1+max(geth(root->left),geth(root->right));
}
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
int res;
int h=geth(root);
int hn=0;
if(root!=nullptr)que.push(root);
while(!que.empty())
{
hn++;
int size=que.size();
for(int i=0;i<size;i++)
{
TreeNode* node=que.front();
que.pop();
res=node->val;
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
if(node->left==nullptr&&node->right==nullptr&&hn==h) return res;
}
}
return -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:
bool isp(TreeNode* root,int t)
{
if(!root->left&&!root->right&&t==0) return true;
if(!root->left&&!root->right) return false;
if(root->left){
if(isp(root->left,t-root->left->val)) return true;
}
if(root->right){
if(isp(root->right,t-root->right->val)) return true;
}
return false;
}
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==nullptr) return false;
return isp(root,targetSum-root->val);
}
};

/**
* 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 {
private:
vector<vector<int>> result;
vector<int> path;
void isp(TreeNode* root,int t)
{
if(!root->left&&!root->right&&t==0) {result.push_back(path);return;}
if(!root->left&&!root->right) return ;
if(root->left){
path.push_back(root->left->val);
isp(root->left,t-root->left->val);
path.pop_back();
}
if(root->right){
path.push_back(root->right->val);
isp(root->right,t-root->right->val);
path.pop_back();
}
return;
}
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
result.clear();
path.clear();
if(root==nullptr) return result;
path.push_back(root->val);
isp(root,targetSum-root->val);
return result;
}
};

学会了手写，但是编程实现呢？下面就是实例。

/**
* 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 {
private:
TreeNode* ft(vector<int>inorder,vector<int>postorder)
{
if(inorder.size()==0) return NULL;
int rootval=postorder[postorder.size()-1];
TreeNode* root=new TreeNode(rootval);
if(postorder.size()==1) return root;
postorder.resize(postorder.size()-1);
int index=0;
for(;index<inorder.size();index++)
{
if(inorder[index]==rootval) break;
}
vector<int> LI(inorder.begin(),inorder.begin()+index);
vector<int> RI(inorder.begin()+index+1,inorder.end());
vector<int> Lpo(postorder.begin(),postorder.begin()+LI.size());
vector<int> Rpo(postorder.begin()+LI.size(),postorder.end());
root->left=ft(LI,Lpo);
root->right=ft(RI,Rpo);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.size()==0||inorder.size()==0) return nullptr;
return ft(inorder,postorder);
}
};

/**
* 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 {
private:
TreeNode* ft(vector<int>preorder,vector<int>inorder)
{
if(inorder.size()==0) return NULL;
int rootval=preorder[0];
TreeNode* root=new TreeNode(rootval);
if(preorder.size()==1) return root;
for(int i=0;i<preorder.size()-1;i++)
preorder[i]=preorder[i+1];
preorder.resize(preorder.size()-1);
int index=0;
for(;index<inorder.size();index++)
{
if(inorder[index]==rootval) break;
}
vector<int> LI(inorder.begin(),inorder.begin()+index);
vector<int> RI(inorder.begin()+index+1,inorder.end());
vector<int> Lpr(preorder.begin(),preorder.begin()+LI.size());
vector<int> Rpr(preorder.begin()+LI.size(),preorder.end());
root->left=ft(Lpr,LI);
root->right=ft(Rpr,RI);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(inorder.size()==0||preorder.size()==0) return nullptr;
return ft(preorder,inorder);
}
};