左叶子之和
思路:我们要遍历一遍二叉树,找到左右子树的左节点之和加起来
int sumOfLeftLeaves(struct TreeNode* root ) { if(root == NULL) return 0; if(root->left == NULL && root->right == NULL) return 0; //判断该节点是否有左节点 if(root->left!=NULL && root->left->right == NULL && root->left->left==NULL) return root->left->val + sumOfLeftLeaves(root->right); return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right); }
思路解释图:
先判断根节点是否为NULL.判断是否没有左右孩子,如果有判断左孩子是否是叶子节点,是的话就存起来这个值,加上右子树的左叶子节点 的值
环形链表的约瑟夫问题
思路:构造一个环形单向循环链表,每走n次,就删除对应的节点,然后直到剩下一个节点
链接：https://www.nowcoder.com/questionTerminal/c3b34059faf546d3a7ee28f2b0154286?toCommentId=18647662 来源：牛客网 #include <stdio.h> #include<stdlib.h> typedef int SDataType; typedef struct StackNode { SDataType val; struct StackNode* next; } StackNode; typedef struct Stack { StackNode* head; int size; } Stack; //创建节点 StackNode* CreateNode(SDataType elemest) { //创建 StackNode* new = (StackNode*)malloc(sizeof(StackNode)); if (new == NULL) { perror("CreateNode"); return NULL; } new->next = NULL; new->val = elemest; return new; } //初始化 void StackInit(Stack* root) { root->head = NULL; root->size = 0; } //插入 void StackPush(StackNode** head, SDataType elemest) { //创建 StackNode* newnode = CreateNode(elemest); if (*head == NULL) { *head = newnode; newnode->next = *head; } else { StackNode* tail = *head; while (tail->next != *head) { tail = tail->next; } tail->next = newnode; newnode->next = *head; } } //删除 void StackPop(StackNode** head, StackNode* node) { if (head == NULL) return; if (*head == node) { StackNode* tail = (*head)->next; while (tail->next != *head) { tail = tail->next; } *head = (*head)->next; tail->next = *head; free(node); return; } StackNode* tail = (*head)->next; while (tail != *head) { if (tail->next == node) break; tail = tail->next; } tail->next = node->next; free(node); } //释放 void StackDestoy(StackNode* head) { StackNode* tail = head->next; while (tail != head) { StackNode* p = tail->next; free(tail); tail = p; } } int main() { // Stack* root = (Stack*)malloc(sizeof(Stack)); //初始化 StackInit(root); int n = 0; scanf("%d", &n); int i = 1; for (i = 1; i <= n; i++) { //插入 StackPush(&(root->head), i); root->size++; } // int m = 0; scanf("%d", &m); int count = 1; StackNode* tail = root->head; while (root->size != 1) { if (count == m) { root->size--; count = 0; //删除 StackNode* p = tail->next; StackPop(&(root->head), tail); tail = p; count++; } else { count++; tail = tail->next; } } printf("%d", root->head->val); StackDestoy(root->head); free(root); return 0; }
