DAY21
513找树左下角的值
自己写的,过了(注意到层序遍历中,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;
- }
- };
递归:
112路径总和
- /**
- * 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);
- }
- };
113路径总和ii
- /**
- * 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;
- }
- };
已学习:由遍历序列构造二叉树_王道数据结构
学会了手写,但是编程实现呢?下面就是实例。
106从中序与后序遍历序列构造二叉树
- /**
- * 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);
- }
- };
105从前序与中序遍历构造二叉树
- /**
- * 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);
- }
- };