当前位置：网站首页>Question brushing notes - tree (easy) - updating
Question brushing notes - tree (easy) - updating
2022-06-27 20:36:00 【Lao Yan is trying】
1. Traversal correlation -DFS
Relatively simple , Don't go into details , Some special notes will be taken
144. Preorder traversal of two tree - Power button （LeetCode）
class Solution {
public:
vector<int>ans;
void DFS(TreeNode* root){
if(root==nullptr)return;
ans.emplace_back(root->val);
DFS(root->left);
DFS(root->right);
}
vector<int> preorderTraversal(TreeNode* root) {
DFS(root);
return ans;
}
};94. Middle order traversal of binary trees - Power button （LeetCode）
class Solution {
public:
vector<int>ans;
vector<int> inorderTraversal(TreeNode* root) {
if(root==nullptr){
return {};
}
if(root->left){
inorderTraversal(root->left);
}
ans.push_back(root->val);
if(root->right){
inorderTraversal(root->right);
}
return ans;
}
};145. Postorder traversal of binary trees - Power button （LeetCode）
class Solution {
public:
vector<int>ans;
void DFS(TreeNode* root){
if(root==nullptr)return;
DFS(root->left);
DFS(root->right);
ans.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
DFS(root);
return ans;
}
};589. N Preorder traversal of a cross tree - Power button （LeetCode）
class Solution {
public:
vector<int>v;
void DFS(Node* root){
if(root==nullptr)return;
v.push_back(root->val);
for(auto x:root->children){
DFS(x);
}
}
vector<int> preorder(Node* root) {
DFS(root);
return v;
}
};590. N The postorder traversal of a cross tree - Power button （LeetCode）
There is a small detail of this problem that deserves attention , Before, I used to declare an overall situation vector To save the results , The method here will vector Pass in the function as an argument , And assign it as a reference , To modify in real time vector The content of .
class Solution {
public:
void helper(const Node* root, vector<int> & res) {
if (root == nullptr) {
return;
}
for (auto & ch : root->children) {
helper(ch, res);
}
res.emplace_back(root->val);
}
vector<int> postorder(Node* root) {
vector<int> res;
helper(root, res);
return res;
}
};2. Traversal correlation -BFS
637. The layer average of a binary tree - Power button （LeetCode）
class Solution {
public:
vector<double>v;
void BFS(TreeNode* root){
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
int n=q.size();
long long sum=0.0;
for(int i=0;i<n;++i){
TreeNode* temp=q.front();
sum+=temp->val;
if(temp->left)q.push(temp->left);
if(temp->right)q.push(temp->right);
q.pop();
}
v.push_back(sum*1.0/n);
}
}
vector<double> averageOfLevels(TreeNode* root) {
BFS(root);
return v;
}
};The finger of the sword Offer 32 - II. Print binary tree from top to bottom II - Power button （LeetCode）
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>res;
if(root==nullptr)return res;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
int n=q.size();
vector<int>temp;
for(int i=0;i<n;++i){
TreeNode* t=q.front();
temp.emplace_back(t->val);
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
q.pop();
}
res.push_back(temp);
}
return res;
}
};102. Sequence traversal of binary tree - Power button （LeetCode）
class Solution {
public:
vector<vector<int>>ans;
void BFS(TreeNode* root){
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
int n=q.size();
vector<int>v;
for(int i=0;i<n;++i){
auto temp=q.front();
v.push_back(temp->val);
if(temp->left)q.push(temp->left);
if(temp->right)q.push(temp->right);
q.pop();
}
ans.push_back(v);
}
}
vector<vector<int>> levelOrder(TreeNode* root) {
if(root==nullptr)return {};
BFS(root);
return ans;
}
};
3. Dual tree correlation
101. Symmetric binary tree - Power button （LeetCode）
The finger of the sword Offer 28. Symmetric binary tree - Power button （LeetCode）
class Solution {
public:
bool check(TreeNode* x,TreeNode* y){
if(x==nullptr && y==nullptr)return true;
if(x==nullptr || y==nullptr)return false;
return x->val==y->val && check(x->left,y->right) && check(x->right,y->left);
}
bool isSymmetric(TreeNode* root) {
return check(root,root);
}
};617. Merge binary tree - Power button （LeetCode）
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1==nullptr)return root2;
if(root2==nullptr)return root1;
auto newNode=new TreeNode(root1->val+root2->val);
newNode->left=mergeTrees(root1->left,root2->left);
newNode->right=mergeTrees(root1->right,root2->right);
return newNode;
}
};100. Same tree - Power button （LeetCode）
The finger of the sword Offer 27. Image of binary tree - Power button （LeetCode）
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==nullptr && q==nullptr)return true;
if(p==nullptr || q==nullptr)return false;
if(p->val!=q->val)return false;
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
};572. The subtree of another tree - Power button （LeetCode）
class Solution {
public:
bool judge(TreeNode* root1,TreeNode* root2){
if(root1==nullptr && root2==nullptr)return true;
if(root1==nullptr || root2==nullptr)return false;
return root1->val==root2->val && judge(root1->left,root2->left) && judge(root1->right,root2->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(root==nullptr || subRoot==nullptr)return false;
return judge(root,subRoot) || isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}
};235. The nearest common ancestor of a binary search tree - Power button （LeetCode）
The finger of the sword Offer 68 - I. The nearest common ancestor of a binary search tree - Power button （LeetCode）
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if((root->val-q->val) * (root->val-p->val)<=0){
return root;
}
return lowestCommonAncestor(p->val<root->val?root->left:root->right,p,q);
}
};236. The nearest common ancestor of a binary tree - Power button （LeetCode）
The finger of the sword Offer 68 - II. The nearest common ancestor of a binary tree - Power button （LeetCode）
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr)return root;
if(root==p || root==q)return root;
TreeNode* L=lowestCommonAncestor(root->left,p,q);
TreeNode* R=lowestCommonAncestor(root->right,p,q);
if(L==nullptr)return R;
if(R==nullptr)return L;
if(L && R)return root;
return nullptr;
}
};4. Depth of tree 、AVL relevant 、 The path of the tree
110. Balanced binary trees - Power button （LeetCode）
The finger of the sword Offer 55 - II. Balanced binary trees - Power button （LeetCode）
class Solution {
public:
int getHeight(TreeNode* root){
if(root==nullptr)return 0;
return max(getHeight(root->left),getHeight(root->right))+1;
}
bool isBalanced(TreeNode* root) {
if(root==nullptr)return true;
return abs( getHeight(root->left) - getHeight(root->right) )<=1 &&
isBalanced(root->left) && isBalanced(root->right);
}
};111. Minimum depth of binary tree - Power button （LeetCode）
class Solution {
public:
int MIN=INT_MAX;
void DFS(TreeNode* root,int currentDep){
if(root==nullptr){
return;
}
if(root->left==nullptr && root->right==nullptr){
MIN=min(MIN,currentDep);
return;
}
DFS(root->left,currentDep+1);
DFS(root->right,currentDep+1);
}
int minDepth(TreeNode* root) {
if(root==nullptr)return 0;
DFS(root,1);
return MIN;
}
};104. The maximum depth of a binary tree - Power button （LeetCode）
class Solution {
public:
int currentDepth=0;
int maxDep=INT_MIN;
void DFS(TreeNode* root){
if(root==nullptr){
return ;
}
currentDepth++;
maxDep=max(maxDep,currentDepth);
DFS(root->left);
DFS(root->right);
currentDepth--;
}
int maxDepth(TreeNode* root) {
if(root==nullptr)return 0;
DFS(root);
return maxDep;
}
};112. The sum of the paths - Power button （LeetCode）
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==nullptr)return false;
if(root->left==nullptr&&root->right==nullptr){
return targetSum==root->val;
}
return hasPathSum(root->left,targetSum-root->val)||hasPathSum(root->right,targetSum-root->val);
}
};257. All paths of binary tree - Power button （LeetCode）
class Solution {
public:
void DFS(TreeNode*root,string s,vector<string>&ans){
if(root){
s+=to_string(root->val);
if(root->left==nullptr && root->right==nullptr){
ans.push_back(s);
}else{
s+="->";
DFS(root->left,s,ans);
DFS(root->right,s,ans);
}
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string>v;
DFS(root,"",v);
return v;
}
};543. The diameter of a binary tree - Power button （LeetCode）
class Solution {
public:
int ans=1;
int deep(TreeNode* root){
if(root==nullptr){
return 0;
}
int L=deep(root->left);
int R=deep(root->right);
ans=max(ans,L+R+1);// The so-called diameter in the title
return max(L,R)+1;// The depth of the subtree
}
int diameterOfBinaryTree(TreeNode* root) {
if(root==nullptr)return 0;
deep(root);
return ans-1;
}
};The finger of the sword Offer 55 - I. The depth of the binary tree - Power button （LeetCode）
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==nullptr)return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
5. Some of the trees trick operation
226. Flip binary tree - Power button （LeetCode）
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr){
return nullptr;
}
swap(root->left,root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};404. Sum of left leaves - Power button （LeetCode）
class Solution {
public:
int sum=0;
void DFS(TreeNode* root){
if(root==nullptr)return;
if(root->left){
if(root->left->left==nullptr && root->left->right==nullptr){
sum+=root->left->val;
}
DFS(root->left);
}
DFS(root->right);
}
int sumOfLeftLeaves(TreeNode* root) {
if(root==nullptr)return 0;
DFS(root);
return sum;
}
};
6. Binary search tree BST
Make good use of BST Is a characteristic of an ordered sequence , Thus, the binary operation can be used , No matter from small to large or from large to small .
108. Convert an ordered array to a binary search tree - Power button （LeetCode）
Interview questions 04.02. Minimum height tree - Power button （LeetCode）
class Solution {
public:
TreeNode* helper(vector<int>& nums,int left,int right){
if(left>right){
return nullptr;
}
int mid=(left+right)>>1;
TreeNode* newNode=new TreeNode(nums[mid]);
newNode->left=helper(nums,left,mid-1);
newNode->right=helper(nums,mid+1,right);
return newNode;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums,0,nums.size()-1);
}
};501. The mode in the binary search tree - Power button （LeetCode）
class Solution {
public:
TreeNode* pre=nullptr;
vector<int>ans;
int cnt=0;
int maxCount=INT_MIN;
void DFS(TreeNode* root){
if(root==nullptr)return;
DFS(root->left);
if(pre==nullptr){
cnt=1;
}else if(pre->val==root->val){
cnt++;
}else{
cnt=1;
}
pre=root;
if(cnt==maxCount){
ans.push_back(root->val);
}
if(cnt>maxCount){
maxCount=cnt;
ans.clear();
ans.push_back(root->val);
}
DFS(root->right);
}
vector<int> findMode(TreeNode* root) {
DFS(root);
return ans;
}
};653. Sum of two numbers IV - Input BST - Power button （LeetCode）
class Solution {
public:
unordered_set<int>m;
bool findTarget(TreeNode* root, int k) {
if(root==nullptr)return false;
if(m.count(k-root->val)==1){
return true;
}
m.insert(root->val);
return findTarget(root->left,k) || findTarget(root->right, k);
}
};700. Search in binary search tree - Power button （LeetCode）
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if(root==nullptr)return nullptr;
if(val==root->val){
return root;
}
return val<root->val?searchBST(root->left, val):searchBST(root->right,val);
}
};The finger of the sword Offer 54. The second of binary search tree k Big node - Power button （LeetCode）
class Solution {
public:
int ans;
void InOrder(TreeNode* root,int &k){
if(root==nullptr)return;
InOrder(root->right,k);
--k;
if(k==0)ans=root->val;
InOrder(root->left,k);
}
int kthLargest(TreeNode* root, int k) {
if(root==nullptr)return 0;
InOrder(root,k);
return ans;
}
};
7. Priority queue （TopK, Heap sort ）
703. The... In the data stream K Big element - Power button （LeetCode）
class KthLargest {
public:
int k;
priority_queue<int,vector<int>,greater<int>>q;
KthLargest(int k, vector<int>& nums) {
this->k=k;
for(auto &i:nums){
add(i);
}
}
int add(int val) {
q.push(val);
if(q.size()>k){
q.pop();
}
return q.top();
}
};
边栏推荐
- database engine
- 键入网址到网页显示，期间发生了什么？
- On the drawing skills of my writing career
- 一段时间没用思源，升级到最新的 24 版后反复显示数据加密问题
- At 19:00 on Tuesday evening, the 8th live broadcast of battle code Pioneer - how to participate in openharmony's open source contribution in multiple directions
- 数据库事务
- 云原生安全指南: 从零开始学 Kubernetes 攻防
- DBeaver恢复和备份数据库的方式
- Summary of redis big key problem handling
- Longitude and latitude analysis
猜你喜欢
【bug】联想小新出现问题，你的PIN不可用。
云原生存储解决方案Rook-Ceph与Rainbond结合的实践
Linux system Oracle 19C OEM monitoring management
Postman 汉化教程(Postman中文版)
[bug] Lenovo Xiaoxin has a problem. Your pin is unavailable.
海量数据出席兰州openGauss Meetup（生态全国行）活动，以企业级数据库赋能用户应用升级
润迈德医疗开启招股：未有基石投资者参与，亏损金额翻倍增长
At 19:00 on Tuesday evening, the 8th live broadcast of battle code Pioneer - how to participate in openharmony's open source contribution in multiple directions
难怪大家丢掉了postman而选择 Apifox
Mongodb introduction and typical application scenarios
随机推荐
Backtracking related issues
Redis集群
UE4 actor Basics
eval函数，全局、本地变量
database engine
openssl客户端编程：一个不起眼的函数导致的SSL会话失败问题
BLE蓝牙模块NRF518/NRF281/NRF528/NRF284芯片方案对比
Mass lucky hash game system development - conflict resolution (code analysis)
【help】JVM的CPU资源占用过高问题的排查
Data intelligence enters the "deep water area", and data governance is the key
ABAP essay - get new crown data through API
数据库锁问题
元宇宙虚拟数字人离我们更近了|华锐互动
CocosCreator播放音频并同步进度
SQL报了一个不常见的错误，让新来的实习生懵了
＃yyds干货盘点＃SQL 子查询
linux系统笑着玩Oracle数据库多表查询-连接查询
【精品必读】Linux系统Oracle数据库趣解子查询
QT Chinese garbled code
[array]bm99 clockwise rotation matrix - simple