递归,一次AC
别人的代码:c++使用Math.max()取最大值
自己迭代迭的乱七八糟
别人的代码:设置一个bool型的全局变量result,迭代中可以修改这个变量。
自己没思路。
使用递归,由叶子结点到根结点,每个结点都返回自己所能贡献的最大直径。设一个全局变量用来在过程中更新diameter。
递归,一次AC。
递归。后面的部分看了标程才写出来。
递归。看了标程才懂。走一步,减一步。
双重递归。一个递归遍历整棵树,用来转换root节点;另一个递归用来返回子树的路径数。
双重递归,一发AC。
别人的,主代码写的更简洁一点
return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
很简单。==注意判空的顺序!==先判if(!t1&&!t2),再判if((!t1&&t2)||(!t2&&t1)||(t1->val!=t2->val)),否则就出bug了。
很简单,一发AC。
看了别人的代码才会做。自己写的只能过一半case。
看了讲解视频后自己写出来了。
dfs子函数中return的是当前连续相同路径(不拐弯),全局变量ans中保存的是历史最大路径。
对递归的用法进一步加深。
看了视频讲解。分类讨论根结点是否被抢。先写出递归,再改成动态规划(后根遍历),否则会TLE。
自己写的,用的后根遍历,AC。
别人的代码,一个节点要么具有 0 个或 2 个子节点,如果有子节点,那么根节点是最小的节点。
自己写的,递归。
看了别人的,用栈实现迭代法。
二叉树的迭代法前、中、后序遍历的整体架构都是一样的,都是while(cur||!s.empty())里面套着一个while(cur)。
注意想象绵羊教授做的整个动态过程,先遍历左边同时放入结果和栈,直到没有左子树时pop节点访问其右子树。
自己写的,递归。
看解析,迭代:从前序遍历到后序遍历:先交换访问左右子树的顺序,然后将整个的结果反转。
前序遍历:center -> left -> right
先变为: center -> right -> left
再反转:left -> right -> center
反转可以通过函数。也可以将vector变为deque,原来是push_back,现在是push_front。
看了讲解才会的。
先一直走左子树走到头,然后再pop。
看了解析,第一次做BFS,BFS要用queue,并且需要size记录每层的个数,这样才知道要pop几个。
BFS,自己AC,注意左下角的值不一定是左子树的值。
看了别人的代码,比我简洁好多。注意调整左右子树入队的顺序,然后合理放置出队的时机,画图模拟一下。
二叉搜索树的左子树的值都小于根结点,右子树的值都大于根结点。
使用递归。
中序遍历二叉搜索树会得到从小到大的排列。
自己一发AC。就是写了一遍中序遍历。
中序遍历的变种,自己一发AC。
也可以用递归的方法,先遍历右子树。
自己一发AC,是669题的变形。
看了讲解,递归。分别取root的左子树的结果,以及root的右子树的结果。如果p和q分别在两个子树,则返回root;如果p和q在同一个子树,则返回那个子树的结果。递归的结束条件是root为空或root等于p或q。
自己是有点递归的思路的,不过还是看了别人的代码。
以后遇到递归还是先考虑单独写一个函数吧,思考起来也清晰一点。
和108题的区别在于,链表不像数组那样可以方便的找到中间的那个数。
所以问题变为,如何找到链表的中间节点。
快慢指针法,有两个指针fast和slow,fast每次走两步,slow每次走一步,当fast->next==NULL||fast->next->next==NULL
时,slow指的就是中间节点。
以后注意不管是链表还是树,写while(fast&&fast->next)这种判断的时候都先加上fast再去判断他的节点是否为空吧,这次就因为这个bug卡了一小时。
对二叉搜索树中序遍历,得到值从小到大的向量。一前一后两个指针检查和是否等于k。
自己一发AC,和上一题思路类似。
思路比较简单,代码比较繁琐。
Trie,又称前缀树或字典树,用于判断字符串是否存在或者是否具有某种字符串前缀。前缀树,根结点不存数据,其他节点需要存储字符和数字,这个数字是0或1,用来标记这个节点是否可以作为字符串的结尾。
注意要写析构函数,因为节点是动态分配内存的,如果只是把树删掉,而没有析构函数的话,会造成内存泄漏。
智能指针,会自动delete,包含在头文件<memory>
中,shared_ptr、unique_ptr、weak_ptr。智能指针不能通过赋值的方式创建,需要按对象的方式创建,使用get()方法获取指针。
// 通过原始指针创建 unique_ptr
std::unique_ptr<TrieNode> root(new TrieNode());
TrieNode* cur=root.get();
可以用两个哈希表,也可以一个哈希表+一个前缀树,还可以纯用前缀树。
两个哈希表:一个哈希表键为word,值为val;另一个哈希表键为前缀,值为前缀和。
哈希表+前缀树:前缀树代替第一种方法中的后一个哈希表。
纯前缀树:求sum的时候需要递归。
// 104
#include <math.h>
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root) return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
// 110
#include <math.h>
class Solution {
public:
bool result=true;
bool isBalanced(TreeNode* root) {
if(!root) return true;
max_deep(root);
return result;
}
int max_deep(TreeNode* root){
if(!root) return 0;
int l1=max_deep(root->left);
int l2=max_deep(root->right);
if(abs(l1-l2)>1) result=false;
return max(l1,l2)+1;
}
};
// 543
#include <math.h>
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int diameter=0;
dfs(root, &diameter);
return diameter;
}
int dfs(TreeNode* root,int* diameter){
if(!root) return 0;
int l1=dfs(root->left,diameter);
int l2=dfs(root->right,diameter);
*diameter = max(*diameter,l1+l2);
return max(l1,l2)+1;
}
};
// 226
TreeNode* invertTree(TreeNode* root) {
if(!root || (!root->left && !root->right)) return root;
TreeNode* temp=root->right;
root->right=invertTree(root->left);
root->left=invertTree(temp);
return root;
}
// 617
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if(!t1) return t2;
if(!t2) return t1;
TreeNode* node=new TreeNode(t1->val+t2->val);
node->left=mergeTrees(t1->left,t2->left);
node->right=mergeTrees(t1->right,t2->right);
return node;
}
// 112
bool hasPathSum(TreeNode* root, int sum) {
if(!root) return false;
if(!root->left && !root->right && root->val==sum) return true;
return hasPathSum(root->left,sum- root->val)||hasPathSum(root->right,sum-root->val);
}
//437
class Solution {
public:
int ans=0;
int pathSum(TreeNode* root, int sum) {
if(!root) return 0;
pathSum(root->left,sum);
pathSum(root->right,sum);
dfs(root,sum);
return ans;
}
int dfs(TreeNode* root,int sum){
if(!root) return 0;
if(root->val==sum) ans++;
dfs(root->left,sum-root->val);
dfs(root->right,sum-root->val);
return 0;
}
};
//572
class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if(!s||!t) return false;
if(isSubtree(s->left,t)) return true;
if(isSubtree(s->right,t)) return true;
return sametree(s,t);
}
bool sametree(TreeNode* s, TreeNode* t){
if(!s&&!t) return true;
if((!s&&t)||(!t&&s)||(s->val!=t->val)) return false;
return sametree(s->left,t->left) && sametree(s->right,t->right);
}
};
// 101
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root) return true;
return sametree(root->left,root->right);
}
bool sametree(TreeNode* t1, TreeNode* t2){
if(!t1&&!t2) return true;
if((!t1&&t2)||(!t2&&t1)||(t1->val!=t2->val)) return false;
return sametree(t1->left,t2->right)&&sametree(t1->right,t2->left);
}
};
// 111
int minDepth(TreeNode* root) {
if(!root) return 0;
if(!root->left &&root->right) return minDepth(root->right)+1;
if(!root->right&&root->left) return minDepth(root->left)+1;
return min(minDepth(root->left),minDepth(root->right))+1;
}
// 404
class Solution {
public:
int ans=0;
int sumOfLeftLeaves(TreeNode* root) {
if(!root) return 0;
if(isleaf(root->left)) return root->left->val+sumOfLeftLeaves(root->right);
return sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
}
bool isleaf(TreeNode* root){
if(!root) return false;
if(!root->left&&!root->right) return true;
return false;
}
};
//687
#include <math.h>
class Solution {
public:
int ans=0;
int longestUnivaluePath(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode* root){
if(!root||(!root->left&&!root->right)) return 0;
int t1=dfs(root->left);
int t2=dfs(root->right);
int leftPath=(root->left&&root->val==root->left->val)?t1+1:0;
int rightPath=(root->right&&root->val==root->right->val)?t2+1:0;
ans=max(ans,leftPath+rightPath);
return max(leftPath,rightPath);
}
};
//337
#include <math.h>
class Solution {
public:
int rob(TreeNode* root) {
int* ans=postRoot(root);
return max(ans[0],ans[1]);
}
int* postRoot(TreeNode* root){
if(!root) return new int [] {0,0};
int* l = postRoot(root->left);
int* r = postRoot(root->right);
int* res = new int[2];
res[0] = max(l[0],l[1])+max(r[0],r[1]);
res[1] = l[0]+r[0]+root->val;
return res;
}
};
//671
int findSecondMinimumValue(TreeNode* root) {
if(!root||(!root->left&&!root->right)) return -1;
int left = root->left->val;
int right = root->right->val;
if(root->val==left) left = findSecondMinimumValue(root->left);
if(root->val==right) right = findSecondMinimumValue(root->right);
if(left!=-1&&right!=-1) return min(left,right);
if(left==-1) return right;
return left;
}
//144
//递归:
class Solution {
public:
vector<int> ans;
vector<int> preorderTraversal(TreeNode* root) {
if(root) ans.push_back(root->val);
else
{
return ans;
}
ans = preorderTraversal(root->left);
ans = preorderTraversal(root->right);
return ans;
}
};
//迭代
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode* cur=root;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
res.push_back(cur->val);
cur=cur->left;
}
cur=s.top()->right;
s.pop();
}
return res;
}
//145
//递归:
class Solution {
public:
vector<int> ans;
vector<int> postorderTraversal(TreeNode* root) {
if(!root) return ans;
ans = postorderTraversal(root->left);
ans = postorderTraversal(root->right);
ans.push_back(root->val);
return ans;
}
};
//迭代
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
deque<int> res;
TreeNode* cur = root;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
res.push_front(s.top()->val);
cur=cur->right;
}
cur=s.top()->left;
s.pop();
}
return vector<int>(res.begin(),res.end());
}
//94
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> temp;
TreeNode* cur = root;
while(cur||!temp.empty())
{
while(cur)
{
temp.push(cur);
cur=cur->left;
}
cur = temp.top();
ans.push_back(cur->val);
temp.pop();
cur=cur->right;
}
return ans;
}
//637
vector<double> averageOfLevels(TreeNode* root) {
vector<double> res;
if(!root) return res;
queue<TreeNode*> s;
s.push(root);
while(!s.empty())
{
int size=s.size();
double sum=0;
for(int i=0;i<size;i++)
{
TreeNode* cur=s.front();
sum+=(cur->val);
s.pop();
if(cur->left) s.push(cur->left);
if(cur->right) s.push(cur->right);
}
res.push_back(sum/size);
}
return res;
}
//513
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
root = q.front();
q.pop();
if(root->right) q.push(root->right);
if(root->left) q.push(root->left);
}
return root->val;
}
//669
TreeNode* trimBST(TreeNode* root, int L, int R) {
if(!root) return NULL;
if(root->val < L) return trimBST(root->right,L,R);
if(root->val > R) return trimBST(root->left,L,R);
root->left = trimBST(root->left,L,R);
root->right = trimBST(root->right,L,R);
return root;
}
//230
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> s;
vector<int> res;
TreeNode* cur=root;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->left;
}
cur=s.top();
s.pop();
res.push_back(cur->val);
cur=cur->right;
}
return res[k-1];
}
//538
TreeNode* convertBST(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* cur=root;
int t=0;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->right;
}
cur=s.top(); s.pop();
cur->val+=t;
t=cur->val;
cur=cur->left;
}
return root;
}
//236
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root||root==p||root==q) return root;
TreeNode* left=lowestCommonAncestor(root->left,p,q);
TreeNode* right=lowestCommonAncestor(root->right,p,q);
if(!left) return right;
if(!right) return left;
return root;
}
//108
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return BST(nums,0,nums.size());
}
TreeNode* BST(vector<int>& nums,int L,int R){
if(L>=R) return NULL;
int n=(R+L)/2;
TreeNode *root=new TreeNode(nums[n]);
root->left=BST(nums,L,n);
root->right=BST(nums,n+1,R);
return root;
}
};
//109
TreeNode* sortedListToBST(ListNode* head) {
if(!head) return NULL;
if(!head->next) return new TreeNode(head->val);
ListNode *fast=head, *slow=head;
ListNode *prev=head;
while(fast&&fast->next)
{
fast=fast->next->next;
prev=slow;
slow=slow->next;
}
TreeNode *root=new TreeNode(slow->val);
prev->next=NULL;
root->left=sortedListToBST(head);
root->right=sortedListToBST(slow->next);
return root;
}
//653
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
vector<int> ans;
inorder(root,ans);
int i=0, j=ans.size()-1;
if(2*ans[0]>k||2*ans[j]<k) return false;
while(i!=j)
{
int temp=ans[i]+ans[j];
if(temp==k) return true;
if(temp>k) j--;
else i++;
}
return false;
}
void inorder(TreeNode* root, vector<int>& res){
if(!root) return;
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right,res);
}
};
//530
#include <math.h>
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
vector<int> res;
inorder(root, res);
int mmin=res[res.size()-1];
for(int i=0;i<res.size()-1;i++)
{
mmin = min(mmin,res[i+1]-res[i]);
}
return mmin;
}
void inorder(TreeNode* root,vector<int>& res){
if(!root) return;
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
};
//501
#include <math.h>
class Solution {
public:
TreeNode *prev=NULL;
int temp;
int num=1;
int maxnum=1;
vector<int> findMode(TreeNode* root) {
vector<int> res;
inorder(root,res);
return res;
}
void inorder(TreeNode* root, vector<int>& res){
if(!root) return ;
inorder(root->left,res);
if(!prev)
{
prev=root;
res.push_back(prev->val);
}
else
{
if(root->val==prev->val)
num++;
else
{
prev=root;
num=1;
}
if(num>maxnum)
while(!res.empty()) res.pop_back();
if(num>=maxnum)
{
res.push_back(root->val);
maxnum=max(num,maxnum);
}
}
inorder(root->right,res);
}
};
//208
class Trie {
private:
struct TrieNode{
bool isword;
vector<TrieNode*> child;
TrieNode():isword(false), child(26,nullptr){}
~TrieNode(){
for(TrieNode* node:child)
if(node) delete node;
}
};
TrieNode* find(const string& word){
TrieNode* cur=root_.get();
for(char c:word){
if(cur->child[c-'a'])
cur=cur->child[c-'a'];
else return nullptr;
}
return cur;
}
public:
std::unique_ptr<TrieNode> root_;
/** Initialize your data structure here. */
Trie(): root_(new TrieNode()) {}
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode* cur=root_.get();
for(char c:word){
if(!cur->child[c-'a'])
cur->child[c-'a']=new TrieNode();
cur=cur->child[c-'a'];
}
cur->isword=true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode* cur=find(word);
if(cur&&cur->isword) return true;
return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
return find(prefix)!=nullptr;
}
};
//677
class MapSum {
private:
struct TrieNode
{
int val;
vector<TrieNode*> child;
TrieNode():val(0), child(26,nullptr){}
~TrieNode(){
for(auto c:child)
if(c!=nullptr) delete c;
}
};
public:
/** Initialize your data structure here. */
std::unique_ptr<TrieNode> root_;
unordered_map<string, int> vals_;
MapSum(): root_(new TrieNode()) {}
void insert(string key, int val) {
TrieNode *cur=root_.get();
int cha=val-vals_[key];
vals_[key]=val;
for(auto c:key)
{
if(cur->child[c-'a']==nullptr)
cur->child[c-'a']=new TrieNode();
cur=cur->child[c-'a'];
cur->val+=cha;
}
}
int sum(string prefix) {
TrieNode *cur=root_.get();
for(auto c:prefix)
{
cur=cur->child[c-'a'];
if(cur==nullptr) return 0;
}
return cur->val;
}
};