#129求根到叶数字之和
回溯放进vector,然后从后往前拿,乘1 10 100 ... 很基础的回溯
my code:
void backtrack(int depth, TreeNode* cur, vector<TreeNode*> &vec, int &sum){
if(cur->left==nullptr &&cur->right==nullptr){
size_t a=1;
for(int i=vec.size()-1;i>=0;i--){
sum+=vec[i]->val*a;
a*=10;
}
return;
}
if(cur->left){
vec.push_back(cur->left);
backtrack(depth+1,cur->left, vec, sum);
vec.pop_back();
}
if(cur->right){
vec.push_back(cur->right);
backtrack(depth+1,cur->right,vec, sum);
vec.pop_back();
}
}
int sumNumbers(TreeNode* root) {
int sum=0;
vector<TreeNode*> vec={root};
backtrack(1,root,vec,sum);
return sum;
}
随想录跟我思路差不多,但这两个是放globa的:int result; vector<int> path; 最近总觉得global不安全不想放
#1382二叉树变平衡
本来遇到这种会换root的就头疼,然后看了眼随想录,是要先变成vec,再从vec重构,就会了
mycode:文章来源:https://www.toymoban.com/news/detail-620210.html
vector<int> vec;
void inorder(TreeNode* node){
if(node==nullptr) return;
inorder(node->left);
vec.push_back(node->val);
inorder(node->right);
}
TreeNode* build_tree(int start, int end){
if(start>end) return nullptr;
TreeNode* root= new TreeNode();
int mid=(start+end)/2;
int val=vec[mid];
root->val=val;
root->left=build_tree(start, mid-1);
root->right=build_tree(mid+1, end);
return root;
}
TreeNode* balanceBST(TreeNode* root) {
inorder(root);
return build_tree(0,vec.size()-1);
}
#100相同的树 easy
以任何方式遍历比较即可:和随想录一模一样文章来源地址https://www.toymoban.com/news/detail-620210.html
bool traverse(TreeNode* n1, TreeNode* n2){
if(n1==nullptr && n2==nullptr) return true;
if(n1==nullptr && n2) return false;
if(n1 && n2==nullptr) return false;
if(n1->val!=n2->val) return false;
return traverse(n1->left, n2->left) && traverse(n1->right, n2->right);
}
bool isSameTree(TreeNode* p, TreeNode* q) {
return traverse(p,q);
}
到了这里,关于代码随想录额外题目| 二叉树 ●129求根到叶数字之和 ●1382二叉树变平衡●100相同的树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!