链表模拟加法
面试题 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; //树的总值==左右子树与根值和 } };
