初级算法-树

二叉树的最大深度

题意：

如题

解：

简单的树搜索操作，DFS和BFS

代码：

#include<bits/stdc++.h>
using namespace std;
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) {}
};
int dfs(TreeNode* root)
{int ans=1;if(root->left!=nullptr) ans=max(ans,1+dfs(root->left));if(root->right!=nullptr) ans=max(ans,1+dfs(root->right));return ans;
}
int bfs(TreeNode* root)
{int n=0;queue<TreeNode*>q;q.push(root);while(true){queue<TreeNode*>temp;while(!q.empty()){TreeNode* nn=q.front();q.pop();if(nn->left!=nullptr) temp.push(nn->left);if(nn->right!=nullptr) temp.push(nn->right);}q=temp;n++;if(q.empty()) break;}return n;
}
int maxDepth(TreeNode* root)
{if(root==nullptr) return 0;int ans1=dfs(root);cout<<"ans1:"<<ans1<<endl;int ans2=bfs(root);cout<<"ans2:"<<ans2<<endl;return ans1;
}
int main()
{}

验证二叉搜索树

题意：

一个二叉搜索树，要求有效条件：左子树严格小于父节点，右子树严格大于父节点且，且子节点的子树也要尊称这个条件

解：

dfs标记区间，蛮好写的

中序遍历，二叉搜索树的中序遍历是递增的，，很有趣

代码：

#include<iostream>
#include<climits>
using namespace std;
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) {}
};
bool zxbl(TreeNode* root,long long &val)//longlong 中序遍历
{bool ans=true;if(root->left!=nullptr) ans&=zxbl(root->left,val);if(root->val>val) val=root->val;else ans=false;if(root->right!=nullptr) ans&=zxbl(root->right,val);return ans;
}
bool dfs(TreeNode* root,long long l,long long r)//longlong dfs 
{bool ans=true;if(root->val<=l || root->val>=r) return false;if(root->left!=nullptr){ans=dfs(root->left,l,root->val);if(!ans) return ans;}if(root->right!=nullptr){ans=dfs(root->right,root->val,r);if(!ans) return ans;}return ans;
}
bool isValidBST(TreeNode* root)
{//long long l=(long long)INT_MIN-1,r=(long long)INT_MAX+1;long long temp=(long long)INT_MIN-1;//bool ans=dfs(root,l,r);bool ans=zxbl(root,temp);cout<<ans<<endl;return ans;
}
int main()
{}

对称二叉树

题意：

一个二叉树判断是否对称

解：

成对访问就行

代码：

#include<bits/stdc++.h>
#include<climits> 
using namespace std;
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) {}
};
bool dfs(TreeNode* root1,TreeNode* root2)//dfs 递归 
{bool ans=true;if(root1==nullptr||root2==nullptr) return false;if(root1->val!=root2->val) return false;if(root1->left!=nullptr||root2->right!=nullptr) ans&=dfs(root1->left,root2->right);if(root1->right!=nullptr||root2->left!=nullptr) ans&=dfs(root1->right,root2->left);return ans;
}
typedef pair<TreeNode*,TreeNode*>PTT;
bool isSymmetric(TreeNode* root)//迭代 
{bool ans=true;PTT ptt;queue<PTT>PTT_q;PTT_q.push({root,root});while(true){queue<PTT>PTT_temp;while(!PTT_q.empty()){ptt=PTT_q.front();PTT_q.pop();if(ptt.first==nullptr||ptt.second==nullptr){ans=false;break;}if(ptt.first->val!=ptt.second->val){ans=false;break;}if(ptt.first->left!=nullptr||ptt.second->right!=nullptr) PTT_temp.push({ptt.first->left,ptt.second->right});if(ptt.first->right!=nullptr||ptt.second->left!=nullptr) PTT_temp.push({ptt.first->right,ptt.second->left});}PTT_q=PTT_temp;if(!ans||PTT_q.empty()) break;}return ans;
}
/*
bool isSymmetric(TreeNode* root)
{bool ans=dfs(root,root);cout<<ans<<endl;return ans;
}*/
int main()
{}

二叉树的层序遍历

题意：

如题

解：

BFS板子

代码：

#include<bits/stdc++.h>
#include<climits> 
using namespace std;
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) {}
};
vector<vector<int>> levelOrder(TreeNode* root)
{vector<vector<int>>ans;if(root==nullptr) return ans;queue<TreeNode*>q;q.push(root);while(true){vector<int>an;queue<TreeNode*>next;while(!q.empty()){TreeNode* temp=q.front();q.pop();an.push_back(temp->val);if(temp->left!=nullptr) next.push(temp->left);if(temp->right!=nullptr) next.push(temp->right);}ans.push_back(an);q=next;if(q.empty())break;}return ans;
}
int main()
{}

将有序数组转换为二叉搜索树

题意：

如题，需要转换成高度平衡二叉树

解：

建搜索二叉树板子add+高度平衡思维ph

为了让高度平衡，左右两边子节点数量差要小于等于1，所以每次从有序数组中取中间，然后对左右区间再建树

代码：

#include<bits/stdc++.h>
#include<climits> 
using namespace std;
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) {}
};
void add(TreeNode* node,int &nums)
{if(node->val==nums) return;if(node->val>nums){if(node->left!=nullptr) add(node->left,nums);else node->left=new TreeNode(nums);}if(node->val<nums){if(node->right!=nullptr) add(node->right,nums);else node->right=new TreeNode(nums);}
}
void ph(TreeNode* &node,int l,int r,vector<int>& nums)
{if(l>r) return;int mid=(l+r)>>1;if(node==nullptr) node=new TreeNode(nums[mid]);else{cout<<"add:"<<nums[mid]<<endl;add(node,nums[mid]);}ph(node,l,mid-1,nums);ph(node,mid+1,r,nums);
}
TreeNode* sortedArrayToBST(vector<int>& nums)
{int lg=nums.size();TreeNode* root=nullptr;ph(root,0,lg-1,nums);return root;
}
int main()
{}