目录
链表模拟加法
面试题 02.05. 链表求和 - 力扣（LeetCode）
思路：
每次取两个链表的对应节点，求和之后将其放入新节点，并尾部插入到新链表，因为链表是反向存
储，直到将两个链表求解结束，值得注意的是，两个数
的长度不一定相同，所以在一个链表结束之
后，还需判断另一个链表是否是有剩余节点。
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head=nullptr,*tail=nullptr;
int wei=0;
while(l1||l2)
{
int n1=l1?l1->val:0;
int n2=l2?l2->val:0;
int sum=n1+n2+wei;
if(!head) head=tail=new ListNode(sum%10);
else
{
tail->next=new ListNode(sum%10);
tail= tail->next;
}
wei=sum/10;
if(l1) l1=l1->next;
if(l2) l2=l2->next;
}
if(wei>0) tail->next=new ListNode(wei);
return head;
}
};数组模拟栈
思路：
检查栈顶的两个元素是否符合删除标准，符合则删除这两个;模拟栈并非直接删除元素，而是移动下标不去访问删除元素，‘\0’确定字符数组结尾，防止访问到删除的元素
class Solution {
public:
string makeGood(string s) {
char st[101];
int top=0;
for(int i=0;i<s.size();i++)
{
st[top++]=s[i];
if(top>=2&&(st[top-1]+32==st[top-2] || st[top-2]+32==st[top-1]))
top-=2;
}
st[top]='\0';
return st;
}
};二进制转整数（二叉树）
思路：
经典遍历二叉树，按题目要求加特判回溯
class Solution {
public:
int dfs(TreeNode *root, int val) {
if (root == nullptr) {
return 0;
}
val = val*2 + root->val; //遍历路径并转为十进制
//当到底的时候才返回路径总值（回溯）
if (root->left == nullptr && root->right == nullptr) {
return val;
}
return dfs(root->left, val) + dfs(root->right, val);
}
int sumRootToLeaf(TreeNode* root) {
return dfs(root, 0);
}
};
巧妙利用二叉树遍历性质
?思路：
利用后序遍历（左右中），求每左右子树和时顺便计算坡度，将坡度累加就是整颗数的坡度；
曲线救国：看似求整颗数的结点之和，实则求坡度
class Solution {
public:
int ans = 0; //坡度
int findTilt(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode* node) {
if (node == nullptr) {
return 0;
}
//后序遍历
int sumLeft = dfs(node->left); //左子树的总和
int sumRight = dfs(node->right); //右子树的总和
ans += abs(sumLeft - sumRight); //坡度计算
return sumLeft + sumRight + node->val; //树的总值==左右子树与根值和
}
};