代码拉取完成,页面将自动刷新
/**
* 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) {}
* };
*/
//转为一维动态规划了
int numTrees(int n) {
vector<int> f(n+1,0);
f[0]=1;
f[1]=1;
for(int i=2;i<=n;++i){
for(int k=1;k<=i;++k)
f[i]+=f[k-1]*f[i-k];
}
return f[n];
}
//[验证二叉搜索树 - 验证二叉搜索树 - 力扣(LeetCode)](https://leetcode.cn/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/)
//作者的思路没问题,主要在这个类型上,导致用例没有完全通过
bool isValidBST(TreeNode* root) {
return isValidBST(root, LONG_MIN, LONG_MAX);
//return isValidBST(root, INT_MIN, INT_MAX);
}
//bool isValidBST(TreeNode *root, int lower, int upper){
bool isValidBST(TreeNode *root, long long lower, long long upper){
if(root==nullptr) return true;
return root->val > lower && root->val < upper && isValidBST(root->left,lower,root->val) && isValidBST(root->right, root->val, upper);
}
//题解的答案
bool helper(TreeNode* root, long long lower, long long upper) {
if (root == nullptr) {
return true;
}
if (root -> val <= lower || root -> val >= upper) {
return false;
}
return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
}
bool isValidBST(TreeNode* root) {
return helper(root, LONG_MIN, LONG_MAX);
}
//递归
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
traverse(root,1,result);
return result;
}
void traverse(TreeNode *root, size_t level, vector<vector<int>> &result){
if(!root) return;
if(level>result.size())
result.push_back(vector<int>());
result[level-1].push_back(root->val);
traverse(root->left,level+1,result);
traverse(root->right,level+1,result);
}
int maxDepth(TreeNode* root) {
return root? 1 + max(maxDepth(root->left), maxDepth(root->right)): 0;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTree(begin(preorder),end(preorder),begin(inorder),end(inorder));
}
template<typename InputIterator>
TreeNode* buildTree(InputIterator pre_first, InputIterator pre_last, InputIterator in_first, InputIterator in_last){
if(pre_first == pre_last) return nullptr;
if(in_first == in_last) return nullptr;
auto root = new TreeNode(*pre_first);
auto inRootPos = find(in_first, in_last, *pre_first);
auto leftSize = distance(in_first, inRootPos);
root->left = buildTree(next(pre_first),next(pre_first,leftSize+1),in_first,next(in_first,leftSize));
root->right=buildTree(next(pre_first,leftSize+1),pre_last,next(inRootPos),in_last);
return root;
}
//递归
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
traverse(root,1,result);
std::reverse(result.begin(),result.end());//与102的差异在这一行
return result;
}
void traverse(TreeNode *root, size_t level, vector<vector<int>> &result){
if(!root) return;
if(level>result.size())
result.push_back(vector<int>());
result[level-1].push_back(root->val);
traverse(root->left,level+1,result);
traverse(root->right,level+1,result);
}
// 主函数
bool isBalanced(TreeNode* root) {
return helper(root) != -1;
}
// 辅函数
int helper(TreeNode* root) {
if (!root) {
return 0;
}
int left = helper(root->left), right = helper(root->right);
if (left == -1 || right == -1 || abs(left - right) > 1) {
return -1;
}
return 1 + max(left, right);
}
//另一个代码实现,思路应该是一样的
bool isBalanced(TreeNode* root) {
return balancedHeight(root) >= 0;
}
//returns the height of root, if root is a balanced tree, otherwise, returns -1
int balancedHeight(TreeNode *root){
if(root == nullptr) return 0; //终止
int left = balancedHeight(root->left);
int right = balancedHeight(root->right);
if(left<0 || right<0 || abs(left-right)>1) return -1; //剪枝
return max(left,right)+1;
}
// 主函数
bool isSymmetric(TreeNode *root) {
return root? isSymmetric(root->left, root->right): true;
}
// 辅函数
bool isSymmetric(TreeNode* left, TreeNode* right) {
if (!left && !right) {
return true;
}
if (!left || !right) {
return false;
}
if (left->val != right->val) {
return false;
}
return isSymmetric(left->left, right->right) && isSymmetric(left->right,
right->left);
}
//递归版
int minDepth(TreeNode* root) {
return minDepth(root,false);
}
static int minDepth(TreeNode *root, bool hasbrother){
if(!root) return hasbrother ?INT_MAX:0;
return 1+min(minDepth(root->left, root->right != NULL),
minDepth(root->right, root->left != NULL));
}
//迭代版
int minDepth(TreeNode* root) {
if(root==nullptr) return 0;
int result = INT_MAX;
stack<pair<TreeNode*,int>> s;
s.push(make_pair(root,1));
while(!s.empty()){
auto node = s.top().first;
auto depth = s.top().secnod;
s.pop();
if(node->left == nullptr && node->right == nullptr)
result = min(result, depth);
if(node->left && result > depth) //深度控制,剪枝
s.push(make_pair(node->left,depth+1));
if(node->right && result > depth) //深度控制,剪枝
s.push(make_pair(node->right,depth+1));
}
return result;
}
bool hasPathSum(TreeNode *root, int sum) {
if(root == nullptr) return false;
if(root->left==nullptr && root->right == nullptr) //leaf
return sum = root->val;
return hasPathSum(root->left, sum-root->val)
|| hasPathSum(root->right, sum-root->val);
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> result;
vector<int> cur; //中间结果
pathSum(root, targetSum, cur, result);
return result;
}
void pathSum(TreeNode *root, int gap, vector<int> &cur, vector<vector<int>> &result){
if(root == nullptr) return;
cur.push_back(root->val);
if(root->left == nullptr && root->right == nullptr) { //leaf
if(gap == root->val)
result.push_back(cur);
}
pathSum(root->left, gap-root->val,cur,result);
pathSum(root->right, gap-root->val,cur,result);
cur.pop_back();
}
void preorder(TreeNode* root, vector<int> &res){
if(root==NULL) return;
res.push_back(root->val);
preorder(root->left,res);
preorder(root->right,res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorder(root, res);
return res; }
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。