以方法、数据结构分类

7.整数反转

1
2
3
4
5
6
7
8
9
10
11
int reverse(int x){
    long a = 0;
    while(x)
    {
        a = a * 10 + (x % 10);  
        x /= 10;
    }
    if(a > INT_MAX || a < INT_MIN)
        return 0;
    else return a;
}

9.回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isPalindrome(int x){
    if(x == 0)
        return true;
    if(x < 0 || x%10 == 0)
        return false;
    long a = 0;
    long t = x;
    while(x)
    {
        a = a * 10 + (x % 10);
        x /= 10;
    }
    if(a == t)
        return true;
    else return false;
}

13.罗马数字转整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
int romanToInt(char * s){
    int i, re = 0;
    
    for(i = 0; i < strlen(s); i++)
    {   
        if(s[i] == 'V')
            re += 5;
        if(s[i] == 'L')
            re += 50;
        if(s[i] == 'D')
            re += 500;
        if(s[i] == 'M')
            re += 1000;
        if(s[i] == 'I')
        {
            if(s[i+1] == 'V')
            {   re += 4;
                i++;
                continue;        // 跳过下一位不计算
            }
            else if(s[i+1] == 'X')
            {   re += 9;
                i++;
                continue;
            }
            else if(s[i+1] != 'V' && s[i+1] != 'X')
                re++;
        }
        if(s[i] == 'X')
        {
            if(s[i+1] == 'L')
            {   re += 40;
                i++;
                continue;
            }
            else if(s[i+1] == 'C')
            {   re += 90;
                i++;
                continue;
            }
            else if(s[i+1] != 'L' && s[i+1] != 'C')
                re += 10;;
        }
        if(s[i] == 'C')
        {
            if(s[i+1] == 'D')
            {   re += 400;
                i++;
                continue;
            }
            else if(s[i+1] == 'M')
            {   re += 900;
                i++;
                continue;
            }
            else if(s[i+1] != 'D' && s[i+1] != 'M')
                re += 100;
        }
    }
    return re;
}

双指针

14.最长公共前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
char * longestCommonPrefix(char ** strs, int strsSize){
    if(strsSize == 0) return "";
    if(strsSize == 1) return strs[0];
    int i, j;
    for(i = 1; i < strsSize; i++)    // 遍历除第一个字符串外的数组，相当于以第一个为基准
    {
        for(j = 0; j < strlen(strs[0]); j++)    // 遍历每个字符
        {
            if(strs[0][j] != strs[i][j])    // 若开始用出现不相等的情况
            {
                strs[0][j] = '\0';        // 就在此处截断字符串
                break;
            }
        }
    }
    return strs[0];
}

26.删除有序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
12
int removeDuplicates(int* nums, int numsSize) {
    int head = 0, rear;
    for(rear = 1; rear < numsSize; rear++) {
		if(nums[rear] == nums[head]) {
            continue;
        } // 发现相等，rear继续后移
        else {
            nums[++head] = nums[rear];
        } // 出现了不等，将head下一位直接覆盖，同时移动head
    }
    return head + 1;
}

80.删除有序数组中的重复项Ⅱ

1
2
3
4
5
6
7
8
9
10
int removeDuplicates(int* nums, int numsSize) {
    if(numsSize <= 2) return numsSize;
    int head = 2, rear;
    for(rear = 2; rear <numsSize; rear++) {
		if(nums[head - 2] != nums[rear]) {
			nums[head++] = nums[rear];
        } // 与上题相比，比较的步长变为2
    }
    return head;
}

88.合并两个有序数组

1
2
3
4
// 题目关键要求：合并后的数组应保存在nums1中
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    
} // 从头开始的双指针涉及元素覆盖问题，故需要再开一个新数组读入最后循环赋值，从nums1尾部开始双指针最优

151.翻转字符串里的单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
char* reverseWords(char* s){
  int len = strlen(s);
  if(len == 0) return s;
  int i = len - 1;
  int num = 0;
  int g = 0;
  while(s[g] == ' '){
      g++;
  }                   //寻找单词开始的位置，作为后面的循环结束条件
  if(g == len) return "";  //用例里面有字符串只有空格的情况，比如"   "
  char * res = (char*)malloc(sizeof(char)*(len+1));
  while(i != g - 1){
     while(i >= 0 && s[i] == ' '){
         i--;        //从后往前找到第一个不是空格的位置
     }
      int j = i;      //从当前位置出发
     while(j >= 0 && s[j] != ' '){
         j--;      //找到第一个是空格的位置
     }
     for(int k = j + 1; k <= i; k++){
         res[num++] = s[k];    //将找到的单词存放在结果数组里面
     }
      res[num++] = ' ';    //单词结束之后添加空格
      i = j;             //接着寻找下一个单词
   }
   res[num - 1] = '\0';   //勿忘！
   return res;
}

167.两数之和Ⅱ - 输入有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    *returnSize = 2;
    int head = 0, rear = numbersSize - 1;
    while(head < rear) {
        if(numbers[head] + numbers[rear] == target) {
            break;
        }
        else if(numbers[head] + numbers[rear] > target) {
            rear--;
        }
        else if(numbers[head] + numbers[rear] < target) {
            head++;
        }
    }
    int *index = (int*)malloc(sizeof(int)*2);
    index[0] = head + 1;
    index[1] = rear + 1;
    return index;
}

283.移动零

1
2
3
4
5
6
7
8
9
10
11
12
void moveZeroes(int* nums, int numsSize) {
    int head = 0;
    for(int rear = 0; rear < numsSize; rear++) {
        if(nums[rear]) {
			if(rear > head) {
                nums[head] = nums[rear];
                nums[rear] = 0; // 排好前面的部分即可，后面直接置零
            }
            head++; // 只有在值覆盖操作后才移动head
        }
    }
}

287.寻找重复数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findDuplicate(int* nums, int numsSize) {
    int rear = 0, front = 0;
    do {
        rear = nums[rear];
        front = nums[nums[front]];
    } while (rear != front);//存在圈，第一相遇点

    rear = 0;
    while (rear != front) {
        rear = nums[rear];
        front = nums[front];
    }                       //重跑，第二相遇点即为分支点
    return rear;
}

动态规划

509.斐波那契数

1
2
3
4
5
6
7
8
9
10
11
int fib(int n) {
    if(n == 0) return 0;
    if(n == 1 || n == 2) return 1;
    int prev = 1, curr = 1;
    for(int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

53.最大子序和

1
2
3
4
5
6
7
8
9
10
int maxSubArray(int* nums, int numsSize){
    int dp[numsSize];
    dp[0] = nums[0];
    int max = dp[0];
    for(int i = 1; i < numsSize; i++) {
        dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i];
        if(dp[i] > max) max = dp[i];
    }
    return max;
}

322.零钱兑换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int coinChange(int* coins, int coinsSize, int amount){
    int dp[amount + 1];
    for(int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX - 1;
    } // 将dp数组初始化为最大值，每个位置将用来存储达到对应角标钱数的最少张数
    dp[0] = 0; // 0元->0张
    for(int i = 0; i <= amount; i++) {
        for(int j = 0; j < coinsSize; j++) {
            if(i - coins[j] < 0) continue;
            dp[i] = fmin(dp[i], 1 + (dp[i - coins[j]])); // 每次将更新后的dp[i]比较
        }
    }
    return (dp[amount] == INT_MAX - 1) ? -1 : dp[amount];  
    // 若dp[amount]仍为最大值，则不能组合
}

链表

1
2
3
4
5
6
7
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

21.合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
	struct ListNode *p, *head;
	if(!l1) {
        return l2;
    }
    else if(!l2) {
        return l1;
    }
    // 若为空的判断
    if(l1->val <= l2->val) {
        head = l1;
        l1 = l1->next;
    }
    else {
        head = l2;
        l2 = l2->next;
    }
    // 开头元素最小的链表头结点作为新链表的头结点
    p = head;
    while(l1 && l2) {
        if(l1->val <= l2->val) {
            p->next = l1;
            l1 = l1->next;
        }
        else {
            p->next = l2;
            l2 = l2->next;
        }
        p = p->next;
    }
    // 在均不为空指针的前提下，按次比较填充新链表
    if(l1) {
        p->next = l1;
    }
    else if(l2) {
        p->next = l2;
    }
    // 某一方为空后直接将另一方剩余的部分接到新链表后
    return head;
}

61.旋转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct ListNode* rotateRight(struct ListNode* head, int k){
    if(head == NULL) return NULL;
    struct ListNode* p = head;
    int n = 1;
    while(p->next){
        p = p->next;
        n++; // 计数，为了确定新的头结点的位置
    } 
    p->next = head; // 将链表首尾相连成环
    p = p->next;
    struct ListNode* newHead;
    for(int i = 0; i < (n - k%n - 1); i++) {
        p = p->next; // 移到新的头结点的位置
    }
    newHead = p->next;
    p->next = NULL; // 断开环
    return newHead;
}

83.删除排序链表中重复元素

1
2
3
4
5
6
7
8
9
10
11
12
struct ListNode* deleteDuplicates(struct ListNode* head) {
	if(head == NULL || head->next == NULL) 
        return head;  
	struct ListNode* p = head;
	while(p && p->next) {    // 因为后续要使用p和p->next, 必须提前排除为空的情况，否则报错
		if(p->val == p->next->val) {
			p->next = p->next->next; // 删除操作
		}
		else p = p->next;
	}c
	return head;
}

86.分隔链表

1
2
3
struct ListNode* partition(struct ListNode* head, int x) {
    
}

141.环形链表

1
2
3
4
5
6
7
8
9
10
bool hasCycle(struct ListNode *head) {
    if(head == NULL || head->next == NULL) return false;
	struct ListNode *slow = head, *fast = head;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) return true; // 快慢指针能相遇必成环
    }
    return false; 
}

经典方法：快慢指针

slow每次走一，fast每次走二

应用：判断链表是否存在环、找到环的入口点，找出未知长度单链表的中间节点等

160.相交链表

1
2
3
4
5
6
7
8
9
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
	if(headA == NULL || headB == NULL) return NULL;
    struct ListNode* pA = headA, *pB = headB;
    while(pA != pB) {
        pA = pA == NULL ? headB : pA->next;
        pB = pB == NULL ? headA : pB->next;
        }
        return pA;
}

本题关键在于两链表的长度可以不同。如果两链表长度相同，那么只需两指针同步前进即可轻松解决。当长度不同时，可以先通过遍历得到长度，再提前将较长的链表指针前移两者的长度差位，便可开始同步移动。而所示方法算法更加简洁，将两链表”串联成环“考虑，最终两指针会在交点处相遇。

203.移除链表元素

1
2
3
4
5
6
7
8
9
10
11
12
13
struct ListNode* removeElements(struct ListNode* head, int val) {
	while(head != NULL && head->val == val)
        head = head->next; // 若从头结点开始就与输入val相同则先对头结点进行操作
    struct ListNode* p;
    p = (struct ListNode*)malloc(sizeof(struct ListNode));
    p->next = head; // 若直接令p = head将无法进行删除操作
    while(p->next != NULL) {
        if(p->next->val == val)
            p->next = p->next->next;
        else p = p->next;
    }
    return head;
}

206.反转链表

1
2
3
4
5
6
7
8
9
10
11
struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL || head->next == NULL) return head;
	struct ListNode* pre = NULL, *cur = head, *next = NULL;
    while(cur) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

234.回文链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool isPalindrome(struct ListNode* head) {
	if(head == NULL || head->next == NULL)
        return true;
    struct ListNode *fast=head,*slow=head, *prev=NULL, *next=NULL;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        next = slow->next;
        slow->next = prev;
        prev = slow;
        slow = next;
    } // 快慢指针与反转同时进行
    
    if (fast) {
        slow = slow->next; 
    } // 若链表长度为奇数，则将slow往后移一位（正中间的结点无需比较）
    while(slow) {
        if(slow->val != prev->val) 
            return false;
        slow = slow->next;
        prev = prev->next;
    }
    return true;
}
// 利用快慢指针找到链表中间位置，同时将前半部分链表反转，再将反转后的与原链表中间位置往后部分进行比较

876.链表的中间结点

1
2
3
4
5
6
7
8
9
struct ListNode* middleNode(struct ListNode* head) {
	if(head == NULL || head->next == NULL) return head;
    struct ListNode *fast = head, *slow = head;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

面试题 02.02. 返回倒数第 k 个节点

1
2
3
4
5
6
7
8
9
10
11
12
int kthToLast(struct ListNode* head, int k) {
    struct ListNode* p;
    p = head;
    while(k--) {
        p = p->next;
    } // 使得p与head相差k
    while(p) {
        p = p->next;
        head = head->next;
    }
    return head->val;
}

栈

20.有效的括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool isValid(char * s){
    if (s == NULL || s[0] == '\0') 
    	return true;
    char *stack = (char *)malloc(strlen(s)); 
    int top =0;
    for (int i = 0; s[i]; ++i) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{')
            stack[top++] = s[i];
        else {
            if((--top) < 0)     // 如果没有数据进栈，处理开头即为右括号的输入
            	return false;
            if (s[i] == ')' && stack[top] != '(') 
            	return false;
            if (s[i] == ']' && stack[top] != '[') 
            	return false;
            if (s[i] == '}' && stack[top] != '{') 
            	return false;
        }
    }
    if(top > 0)      // 比较到最后top值应为0，即回退到栈底
        return false;
    return true;
}

算法分析：

利用另一个数组（栈）储存进入栈的值（仅左括号），读取左括号会更新栈顶（储存在stack数组下一个位置），若读到右括号则与栈顶值比较同时栈顶值前移一位为下次比较做准备。

155.最小栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#define min(x, y) (x < y) ? x : y
typedef struct node {
    int val;
    int min;
    int* next;
}Node;
typedef struct stack {
    Node* top;
}MinStack;
/** initialize your data structure here. */

MinStack* minStackCreate() {
    MinStack* p = (MinStack*)malloc(sizeof(MinStack));
    p->top = NULL;
    return p;
}

void minStackPush(MinStack* obj, int x) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = x;
    newNode->next = obj->top;
    if(obj->top == NULL) newNode->min = x;
    else newNode->min = min(x, minStackGetMin);
    obj->top = newNode;
}

void minStackPop(MinStack* obj) {
    if(obj->top == NULL) return;
    Node* newTop = obj->top->next;
    free(obj->top);
    obj->top = newTop;
}

int minStackTop(MinStack* obj) {
    return obj->top->val;
}

int minStackGetMin(MinStack *obj) {
    return  obj->top->min;
}

void minStackFree(MinStack* obj) {
    while(obj->top) {
        minStackPop(obj);
    }
    free(obj);
    obj = NULL;
}

1047.删除字符串中所有相邻重复项

1
2
3
4
5
6
7
8
9
10
11
char * removeDuplicates(char * S) {
    int top = -1;
    char* t = (char*)malloc(strlen(S)*sizeof(char));
    for(int i = 0; i < strlen(S); i++) {
        t[++top] = S[i];
        if(top > 0 && t[top] == t[top - 1])
            top = top - 2;
    }
    t[top + 1] = '\0'; // 新字符串可能比原字符串短，必须在新的末尾终止！
    return t;
}

树

1
2
3
4
5
6
7
8
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

100.相同的树

1
2
3
4
5
6
7
8
9
10
11
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p == NULL && q == NULL) return true;
    if(p == NULL || q == NULL) return false;
    if(p->val == q->val) {
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
    else return false;
}
/* 两树相等条件：1.当前两个树的根节点值相等
2.p的左子树和q的左子树相等
3.p的右子树和q的右子树相等 */

572.另一个树的子树

1
2
3
4
5
6
7
8
9
10
11
12
bool compare(struct TreeNode* s, struct TreeNode* t) {
    if(!s && !t) return true;
    if(!s || !t) return false;
    if(s->val != t->val) return false;
    return compare(s->left, t->left) && compare(s->right, t->right);
}
// compare()与T100“相同的树”逻辑相同
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if(root == NULL) return false;
    return compare(root, subRoot) || isSubtree(root->left, subRoot) || 		                isSubtree(root->right, subRoot);
}
// 判断两树相等的三个条件是“与"的关系，而是否为子树则是”或“的关系，该题将两逻辑结合

1367.二叉树中的列表

1
2
3
4
5
6
7
8
9
10
11
bool compare(struct TreeNode* t, struct ListNode* head) {
    if(head == NULL) return true; // 只要head全遍历到必定存在
    if(t == NULL) return false; // 上行不成立的情况下树遍历完了说明没有
    if(t->val != head->val) return false;
    return compare(t->left, head->next) || compare(t->right, head->next);
}
// 主要与上两题不同在于不是“与”而是“或”——一直连续向下的路径可左可右
bool isSubPath(struct ListNode* head, struct TreeNode* root) {
   if(root == NULL) return false;
    return compare(root, head) || isSubPath(head, root->left) || isSubPath(head,            root->right); 
}

101.对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isMirrorTree(struct TreeNode *p, struct TreeNode *q)
{
    if ((p == NULL) && (q == NULL)) {
        return true;
    } else if ((p == NULL) || (q == NULL)) {
        return false;
    }
    if (p->val != q->val) {
        return false;
    }
    return (isMirrorTree(p->left, q->right)) && (isMirrorTree(p->right, q->left));
}
// 该函数输入两个相同根节点方便递归比较
bool isSymmetric(struct TreeNode* root){
    return isMirrorTree(root, root);
}

104.二叉树的最大深度

1
2
3
4
5
#define max(x, y) x > y ? x : y
int maxDepth(struct TreeNode* root) {
    if(!root) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1; // 二叉树最大深度为左子树深度与右子树深度较大者+1
}

105.从前序遍历与中序遍历构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
	if(preorderSize == 0) return NULL;
    struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->val = preorder[0]; // 唯一赋值操作
    int i = 0;
    for(; inorder[i] != preorder[0]; i++); // i表示中序遍历中当前头结点的位置,同时也可代表当前左子树结点数目
    if(i) {
         root->left = buildTree(preorder+1, i, inorder, i); 
    }
    	 // 根据遍历序列特点调整序列起点、长度
    else root->left = NULL;
    if(i != inorderSize - 1) {
        root->right = buildTree(preorder+i+1, preorderSize-i-1, inorder+i+1, inorderSize-i-1);
    }
    else root->right = NULL;
    return root;
}

106.从中序与后序遍历序列构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
	if(postorderSize == 0) return NULL;
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    int i = 0;
    root->val = postorder[postorderSize - 1];
    for(; inorder[i] != postorder[postorderSize - 1]; i++); // i表示中序遍历中当前头结点的位置,同时也可代表当前左子树结点数目
    if(i) {
        root->left = buildTree(inorder, i, postorder, i);
    }
    else root->left = NULL;
    if(i != inorderSize - 1) {
        root->right = buildTree(inorder + i + 1, inorderSize - i -1, postorder + i, postorderSize - i - 1);
    }
    else root->right = NULL;
    return root;
}

110.平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 平衡二叉树是一种二叉排序树，每一个节点的左子树和右子树的高度差至多等于1
#define max(x, y) x > y ? x : y

int treeHeight(struct TreeNode* root) {
    if(!root) return 0;
    return max(treeHeight(root->left), treeHeigth(root->right)) + 1;
} // 深度计算函数，见T104

bool isBalanced(struct TreeNode* root) {
   if(!root) return true;
   else {
   	return isBalanced(root->left) && isBalanced(root->right) && 
           abs(height(root->left) - height(root->right)) <= 1;
    }
}

226.翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct TreeNode* invertTree(struct TreeNode* root) {
    invert(root);
    return root;
}

void invert(struct TreeNode* root) {
	if(!root) return;
    // 经典交换
    struct TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    // 递归翻转左右子树
    invert(root->left);
    invert(root->right);
}

404.左叶子之和

1
2
3
4
5
6
7
8
int sumOfLeftLeaves(struct TreeNode* root) {
    if(root == NULL) return 0;
    int n = 0;
    if(root->left && !root->left->left && !root->left->right) n = root->left->val;
    /* 判断是否为左叶子：1.左孩子存在
    2.左孩子的左右孩子不存在 */
    return n + sumOfLeftLeaves(root->left) + sunOfLeftLeaves(root->right);
}

235.二叉搜索树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define max(x, y) x > y ? x : y
#define min(x, y) x < y ? x : y

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    int max = max(p->val, q->val);
    int min = min(p->val, q->val);
    struct TreeNode* ret;
    while(root) {
        if(root->val >= min && root->val <= max) {
            ret = root;
            break;
        } // 夹在最大最小值间即为最近公共祖先
        if(root->val > max) {
            root = root->left;
        } // 当前节点的值大于最大值，往左边寻找更小的
        if(root->val < min) {
            root = root->right;
        } // 当前节点的值小于最小值，往右边寻找更大的
    }
    return ret;
}

1382.将二叉搜索树变平衡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void inOrderTraverse(struct TreeNode* root, int* pos, int arr[]) {
    if(root == NULL) return;
    inOrderTraverse(root->left, pos, arr);
    arr[(*pos)++] = root->val;
    inOrderTraverse(root->right, pos, arr);
} 
// 将前序遍历序列存入数组中
struct TreeNode* create(int *nums, int low, int high) {
    if(low > high) return NULL;
    int mid = (low + high) / 2;
    struct TreeNode* t = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t->val = nums[mid];
    t->left = create(nums, low, mid - 1);
    t->right = create(nums, mid + 1, high);
    return t;
}
// 根据前序遍历序列创建一个平衡的二叉树（不唯一）
struct TreeNode* balanceBST(struct TreeNode* root){
    int arr[10000];
    int *pos = (int*)malloc(sizeof(int));
    *pos = 0;
    inOrderTraverse(root, pos, arr);
    return create(arr, 0, *pos - 1);
}