建设电子商务系统网站,大同网站建设站建设,宠物网站建设,韩国企业网站设计文章目录 二叉树的最大深度题意#xff1a;解#xff1a;代码#xff1a; 验证二叉搜索树题意#xff1a;解#xff1a;代码#xff1a; 对称二叉树题意#xff1a;解#xff1a;代码#xff1a; 二叉树的层序遍历题意#xff1a;解#xff1a;代码#xff1a; 将有… 文章目录 二叉树的最大深度题意解代码 验证二叉搜索树题意解代码 对称二叉树题意解代码 二叉树的层序遍历题意解代码 将有序数组转换为二叉搜索树题意解代码 二叉树的最大深度
题意
如题
解
简单的树搜索操作DFS和BFS
代码
#includebits/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 ans1;if(root-left!nullptr) ansmax(ans,1dfs(root-left));if(root-right!nullptr) ansmax(ans,1dfs(root-right));return ans;
}
int bfs(TreeNode* root)
{int n0;queueTreeNode*q;q.push(root);while(true){queueTreeNode*temp;while(!q.empty()){TreeNode* nnq.front();q.pop();if(nn-left!nullptr) temp.push(nn-left);if(nn-right!nullptr) temp.push(nn-right);}qtemp;n;if(q.empty()) break;}return n;
}
int maxDepth(TreeNode* root)
{if(rootnullptr) return 0;int ans1dfs(root);coutans1:ans1endl;int ans2bfs(root);coutans2:ans2endl;return ans1;
}
int main()
{}验证二叉搜索树
题意
一个二叉搜索树要求有效条件左子树严格小于父节点右子树严格大于父节点且且子节点的子树也要尊称这个条件
解
dfs标记区间蛮好写的
中序遍历二叉搜索树的中序遍历是递增的很有趣
代码
#includeiostream
#includeclimits
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 anstrue;if(root-left!nullptr) anszxbl(root-left,val);if(root-valval) valroot-val;else ansfalse;if(root-right!nullptr) anszxbl(root-right,val);return ans;
}
bool dfs(TreeNode* root,long long l,long long r)//longlong dfs
{bool anstrue;if(root-vall || root-valr) return false;if(root-left!nullptr){ansdfs(root-left,l,root-val);if(!ans) return ans;}if(root-right!nullptr){ansdfs(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_MAX1;long long temp(long long)INT_MIN-1;//bool ansdfs(root,l,r);bool anszxbl(root,temp);coutansendl;return ans;
}
int main()
{}对称二叉树
题意
一个二叉树判断是否对称
解
成对访问就行
代码
#includebits/stdc.h
#includeclimits
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 anstrue;if(root1nullptr||root2nullptr) return false;if(root1-val!root2-val) return false;if(root1-left!nullptr||root2-right!nullptr) ansdfs(root1-left,root2-right);if(root1-right!nullptr||root2-left!nullptr) ansdfs(root1-right,root2-left);return ans;
}
typedef pairTreeNode*,TreeNode*PTT;
bool isSymmetric(TreeNode* root)//迭代
{bool anstrue;PTT ptt;queuePTTPTT_q;PTT_q.push({root,root});while(true){queuePTTPTT_temp;while(!PTT_q.empty()){pttPTT_q.front();PTT_q.pop();if(ptt.firstnullptr||ptt.secondnullptr){ansfalse;break;}if(ptt.first-val!ptt.second-val){ansfalse;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_qPTT_temp;if(!ans||PTT_q.empty()) break;}return ans;
}
/*
bool isSymmetric(TreeNode* root)
{bool ansdfs(root,root);coutansendl;return ans;
}*/
int main()
{}二叉树的层序遍历
题意
如题
解
BFS板子
代码
#includebits/stdc.h
#includeclimits
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) {}
};
vectorvectorint levelOrder(TreeNode* root)
{vectorvectorintans;if(rootnullptr) return ans;queueTreeNode*q;q.push(root);while(true){vectorintan;queueTreeNode*next;while(!q.empty()){TreeNode* tempq.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);qnext;if(q.empty())break;}return ans;
}
int main()
{}将有序数组转换为二叉搜索树
题意
如题需要转换成高度平衡二叉树
解
建搜索二叉树板子add高度平衡思维ph
为了让高度平衡左右两边子节点数量差要小于等于1所以每次从有序数组中取中间然后对左右区间再建树
代码
#includebits/stdc.h
#includeclimits
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-valnums) return;if(node-valnums){if(node-left!nullptr) add(node-left,nums);else node-leftnew TreeNode(nums);}if(node-valnums){if(node-right!nullptr) add(node-right,nums);else node-rightnew TreeNode(nums);}
}
void ph(TreeNode* node,int l,int r,vectorint nums)
{if(lr) return;int mid(lr)1;if(nodenullptr) nodenew TreeNode(nums[mid]);else{coutadd:nums[mid]endl;add(node,nums[mid]);}ph(node,l,mid-1,nums);ph(node,mid1,r,nums);
}
TreeNode* sortedArrayToBST(vectorint nums)
{int lgnums.size();TreeNode* rootnullptr;ph(root,0,lg-1,nums);return root;
}
int main()
{}
