Zichuan365' Blog HomeArchivesCategoriesGalleryAbout
LeetCode / 链表、树、二分
|LeetCode树、链表专题

链表

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

};

—————————旋转链表

LC_206.反转链表（最基础的）

1
2
3
4
5
6
7
8
9
10
11
12
//1.递归
ListNode* reverseList(ListNode* head) {
	if (head == NULL || head->next == NULL)
		return head;

	ListNode* temp = head->next;
	ListNode* res = reverseList(temp);//找到最后一个节点,返回head

	temp->next = head;
	head->next = NULL;
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//2.辅助双指针
ListNode* reverseList(ListNode* head) {
	if (head == NULL || head->next == NULL)
		return head;

	ListNode* pre = NULL;
	ListNode* next = NULL;

	while (head) {
		next = head->next;
		head->next = pre;
		pre = head;
		head = next;

	}

	return pre;
}

LC_25. K个一组_反转

  • 给你这个链表：1->2->3->4->5

  • 当 k = 2 时，应当返回: 2->1->4->3->5
  • 当 k = 3 时，应当返回: 3->2->1->4->5

img

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
ListNode* reverseKGroup(ListNode* head, int k) {
	ListNode* returnNode = new ListNode(999);
	returnNode->next = head;

	ListNode* pre = returnNode;
	ListNode* end = returnNode;

	while (end != NULL) {
		for (int i = 0; i < k&&end != NULL; i++)end = end->next;
		if (end == NULL)break;
		//保存开始节点、下一开始节点
		ListNode* start = pre->next;
		ListNode* nextStart = end->next;

		//断开
		end->next = NULL;
		//开始反转
		pre->next = reverse(start);
		//然后接上
		start->next = nextStart;

		//更新数据
		pre = start;
		end = pre;
	}
	return returnNode->next;
}

ListNode* reverse(ListNode* head) {
	if (head == NULL && head->next == NULL)
		return head;

	ListNode* pre = NULL;
	ListNode* next = NULL;
	while (head) {
		next = head->next;
		head->next = pre;
		pre = head;
		head = next;
	}
	return pre;
}

LC_92.第N到M个节点_反转

  • 1.哨兵节点，定位pre、cur节点

  • 2.开始反转

  • 辅助节点pre、cur是不会变化的，next节点不断前移
    img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode* reverseBetween(ListNode* head, int m, int n) {
	//哨兵节点
	ListNode* returnNode = new ListNode(999);
	returnNode->next = head;

	//定位pre节点
	ListNode* pre = returnNode;
	for (int i = 0; i < m - 1; i++)
		pre = pre->next;

	//辅助双节点
	ListNode* cur = pre->next;
	ListNode* next = NULL;

	for (int i = 0; i < n - m; i++) {
		next = cur->next;
		cur->next = next->next;
		next->next = pre->next;
		pre->next = next;
	}
	return returnNode->next;
}

LC_24.相邻节点_反转

  • 反转链表：

  • 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

  • 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

  • 案列：- 给定 1->2->3->4, 你应该返回 2->1->4->3.
    img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ListNode* swapPairs(ListNode* head) {
	ListNode* returnNode = new ListNode(999);
	returnNode->next = head;

	ListNode* cur = returnNode;
	while (cur->next && cur->next->next) {
		ListNode* first = cur->next;
		ListNode* second = cur->next->next;

		//依次改变节点
		cur->next = second;
		first->next = second->next;
		second->next = first;

		//更新cur节点,注意:first和second节点位置,已经发生了变化,只能在原节点的基础上进行修改
		cur = cur->next->next;
	}
	return returnNode->next;
}

—————————————

—————————删除节点

LC_83.排序链表删除重复节点 / 保留一个

  • 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

  • 输入: 1->1->2

  • 输出: 1->2

  • 输入: 1->1->2->3->3

  • 输出: 1->2->3

  • 解：关键是要删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* deleteDuplicates(ListNode* head) {
	if (head == NULL || head->next == NULL)
		return head;

	//注意需要删除节点
	ListNode* cur = head;
	while (cur && cur->next) {
		if (cur->val == cur->next->val) {
			ListNode* temp = cur->next;
			cur->next = cur->next->next;
			delete temp;
		}
		else {
			cur = cur->next;
		}
	}
	return head;
}

LC_82.排序链表删除重复节点 / 不保留

  • 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

  • 输入: 1->2->3->3->4->4->5

  • 输出: 1->2->5

  • 输入: 1->1->1->2->3

  • 输出: 2->3

  • 题解：
    img

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
ListNode* deleteDuplicates(ListNode* head) {
	if (head == NULL || head->next == NULL)
		return head;

	//哨兵节点
	ListNode *returnNode = new ListNode(9999);
	returnNode->next = head;

	ListNode *cur = returnNode;
	while (cur && cur->next) {
		ListNode *first = cur->next;
		ListNode *second = cur->next->next;
		//1.还剩一个节点 或 2.first!=second  满足条件,后移cur指针
		if (second == NULL || first->val != second->val)
			cur = cur->next;
		else {
			//持续排除连续的节点,找到1223中的后面一个2节点位置
			//都用first来写,second节点会发生变化
			while (first->next && first->val == first->next->val)
				first = first->next;

			//舍去这部分重复的
			cur->next = first->next;
		}
	}
	return returnNode->next;
}

链表倒数第K个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
	if (pListHead == NULL || k == 0)
		return NULL;
	ListNode* fast = pListHead;
	ListNode* slow = pListHead;

	//超出范围
	while (k--) {
		if (fast)
			fast = fast->next;
		else {
			return NULL;
		}
	}
	while (fast) {
		fast = fast->next;
		slow = slow->next;
	}
	return slow;
}

LC_19.倒数第K个节点删除(快慢指针)

  • 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

  • 解：

  • 快慢指针实现：注意的是while(fast->next)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode* removeNthFromEnd(ListNode* head, int n) {
	// write code here
	ListNode* fast = head;
	ListNode* slow = head;
	while (n--) {
		if (fast)
			fast = fast->next;
		else
			return NULL;
	}
	if (fast == NULL)
		return head->next;

	//如果时 while(fast)就是指向的第N个节点
	//我需要的是倒数第N-1个节点
	while (fast->next) {
		fast = fast->next;
		slow = slow->next;
	}
	slow->next = slow->next->next;
	return head;
}

—————————————

LC_148.无序链表排序(归并)

  • 时间复杂度O（nlogn）

  • 归并排序：递归，需要额外空间复杂度
  1. 快慢指针、找到中心节点，进行切断
  2. cut->next = NULL;同时先分割再合并
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

ListNode* sortList(ListNode* head) {
	if (!head || !head->next) return head;
	
	//分割链表、快慢指针找出中点
	ListNode *middle = findMiddle(head);

	ListNode* L = sortList(head);
	ListNode* R = sortList(middle);

	return mergeSort(L, R); //采用归并排序有序链表、递归方法
}
//找到中间位置
ListNode *findMiddle(ListNode* head) {
	ListNode *fast = head, *slow = head;
	ListNode *cut;
	while (fast && fast->next)
	{
		cut = slow;//////重要
		slow = slow->next;
		fast = fast->next->next;
	}
	cut->next = NULL; // 这一步很重要！需要把前半部分和后半部分断开
	return slow;
}

//两个链表进行比较合并
ListNode *mergeSort(ListNode *head, ListNode *mid)
{
	ListNode *returnNode = new ListNode(0);

	ListNode *pos = returnNode;
	while (head && mid)
	{
		if (head->val < mid->val){
			pos->next = head;
			head = head->next;
		}
		else{
			pos->next = mid;
			mid = mid->next;
		}
		pos = pos->next;
	}
	if (head != NULL)
		pos->next = head;
	else
		pos->next = mid;

	return returnNode->next;
}

两个链表是否有交点

  • 解法：

    • 1.都不是环形（走A+C+B = B+C+A）
    • 2.一个环一个不是环（无交点）
    • 3.都是环（快慢指针分别找到一个随机点p1、p2。p1往前走能遇到p2有交点）

LC_2.两数相加

  • 输入：L1：(2 -> 4 -> 3) + L2：(5 -> 6 -> 4)

  • 输出：7 -> 0 -> 8
  • 原因：342 + 465 = 807
  • 有点类似归并，一个一个接上去
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
62
63
64
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
	ListNode* head = new ListNode(1);//头节点,用于保存第一个节点信息
	ListNode* res = head;//移动节点

	int sum = 0;
	bool carry = false;
	while (l1 || l2) {
		sum = 0;
		if (l1) {
			sum += l1->val;
			l1 = l1->next;
		}
		if (l2) {
			sum += l2->val;
			l2 = l2->next;
		}
		if (carry)
			sum++;
		res->next = new ListNode(sum % 10);
		res = res->next;

		if (sum >= 10) {
			carry = true;
		}
		else {
			carry = false;
		}
	}
	if (carry)
		res->next = new ListNode(1);
	return head->next;
}

//两数相加——二进制
string cal(string tmp1, string tmp2) {
	string res;

	bool flag = false;

	int p1 = tmp1.size() - 1;
	int p2 = tmp2.size() - 1;

	int sum;
	while (p1 >= 0 || p2 >= 0) {
		sum = 0;
		if (p1 >= 0)
			sum += tmp1[p1--] - '0';
		if (p2 >= 0)
			sum += tmp2[p2--] - '0';
		if (flag)
			sum += 1;
		res += to_string((sum % 2));
		if (sum >= 2)
			flag = true;
		else
			flag = false;
	}
	if(flag)
		res += to_string(1);


	reverse(res.begin(), res.end());
	return res;
}

LC_61.指定向右移动链表K

  • 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

  • 输入: 1->2->3->4->5->NULL, k = 2
  • 输出: 4->5->1->2->3->NULL
  • 解释:
  • 向右旋转 1 步: 5->1->2->3->4->NULL
  • 向右旋转 2 步: 4->5->1->2->3->NULL
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
ListNode* rotateRight(ListNode* head, int k) {
	if (!head || !head->next || k == 0) return head;
	ListNode *vis = head;
	int size = 1;
	//统计链表长度
	while (vis && vis->next) {
		vis = vis->next;
		size++;
	}
	//移动为整数倍,直接返回
	int move = k % size;
	if (move == 0)
		return head;

	//移动不为整数倍,成环再返回
	ListNode *cut = head;
	for (int i = 0; i < size - move - 1; i++)
		cut = cut->next;

	//在此断开
	ListNode *res = cut->next;

	cut->next = NULL;
	vis->next = head;//尾部节点接上头

	return res;
}

LC_138 / J_35. 复制带随机指针的链表

  • 输入

剑指Offer_35 

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
//深拷贝：复制对象 浅拷贝：复制对象的指针
Node* copyRandomList(Node* head) {
	if (head == NULL)return NULL;
	//原地复制链表,且仅将next指针连接起来，例如A->B->C变成A->A'->B->B'->C->C'
	Node* cur = head;
	while (cur) {
		Node* newNode = new Node(cur->val);
		newNode->next = cur->next;
		cur->next = newNode;
		cur = newNode->next;
	}
	cur = head;//cur指针复位
	//第二步复制random指针，A'、B'、C'指到对应的位置
	while (cur) {
		if (cur->random) cur->next->random = cur->random->next;
		cur = cur->next->next;
	}
	//第三步将链表断开，例如A->A'->B->B'->C->C'变为A'->B'->C',且注意这一步应当将原链表复原。
	Node* returnhead = head->next;//A',返回的节点

	Node* copycur = head->next;   //A'
	cur = head; //A
	while (cur) {
		cur->next = cur->next->next;
		cur = cur->next;
		if (copycur->next) {
			copycur->next = copycur->next->next;
			copycur = copycur->next;
		}
	}
	return returnhead;
}

21.合并2个升序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	ListNode* pre = new ListNode(-1);
	ListNode* cur = pre;
	while (l1 != NULL && l2 != NULL) {
		if (l1->val < l2->val) {
			cur->next = l1;
			cur = cur->next;
			l1 = l1->next;
		}
		else {
			cur->next = l2;
			cur = cur->next;
			l2 = l2->next;
		}
	}
	if (l1 == NULL)
		cur->next = l2;
	else
		cur->next = l1;

	return pre->next;
}

23.合并K个升序链表

  • 分治法

    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
    ListNode* mergeKLists(vector<ListNode*>& lists) {
    	return divideAndMerge(lists, 0, lists.size() - 1); // 使用分治策略优化时间效率
    }

    //合并两个有序链表
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    	ListNode* pre = new ListNode(-1);
    	ListNode* cur = pre;
    	while (l1 != NULL && l2 != NULL) {
    		if (l1->val < l2->val) {
    			cur->next = l1;
    			cur = cur->next;
    			l1 = l1->next;
    		}
    		else {
    			cur->next = l2;
    			cur = cur->next;
    			l2 = l2->next;
    		}
    	}
    	if (l1 == NULL)
    		cur->next = l2;
    	else
    		cur->next = l1;

    	return pre->next;
    }
    //类似归并排序:分治法
    ListNode *divideAndMerge(vector<ListNode*> &lists, int l, int r) {
    	if (l == r)
    		return lists[l];
    	if (l > r)
    		return NULL;

    	int mid = (l + r) / 2;
    	return mergeTwoLists(divideAndMerge(lists, l, mid),
    		divideAndMerge(lists, mid + 1, r));
    }

树

1
2
3
4
5
6
struct Node {		//这是二叉树的节点
	Node* left;
	Node* right;
	int value;
	Node(int val) :value(val), left(NULL), right(NULL) {}
};

1.二叉树的层序、先序、中序、后续

1.1层序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void cal(Node* root, vector<int>&res) {
	if (root == NULL)
		return;
	
	queue<Node*>q;
	q.push(root);
	
	while(!q.empty()){
		int size = q.size();
		for (int i = 0; i < size; i++) {
			Node* temp = q.front();
			q.pop();
			res.push_back(temp->value);
			
			if (temp->left)q.push(temp->left);
			if (temp->right)q.push(temp->right);
		}
	}
}

  • 第二种序列化时用：加入#

    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
    string cal(Node* root) {
    	if (root == NULL)
    		return  "";

    	string out;
    	queue<Node*>q;
    	q.push(root);

    	while (!q.empty()) {
    		int size = q.size();
    		for (int i = 0; i < size; i++) {
    			Node* temp = q.front();
    			q.pop();
    			if (temp) {
    				out += to_string(temp->value) + " ";
    				q.push(temp->left);
    				q.push(temp->right);
    			}
    			else {
    				out += "# ";
    			}
    		}
    	}
    	return out;
    }

1.2先序遍历（LeetCode144）

  • 递归：中、左、右

    1
    2
    3
    4
    5
    6
    7
    8
    void preOrder(Node* root) {
    	if (root == NULL)
    		return;
    	
    	cout << root->value;
    	preOrder(root->left);
    	preOrder(root->right);
    }

  • 迭代：利用stack特性来做

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void preorder(Node* head) {		//先序遍历
    	if (head == NULL)
    		return;
    	
    	stack<Node*>q;
    	q.push(head);    //利用栈的特性，先进右孩子   
    	while (!q.empty())
    	{
    		head = q.top();	
    		q.pop();
    		cout << head->value << " ";
    		//先进右孩子，stack后输出右孩子
    		if (head->right)q.push(head->right);
    		if (head->left)q.push(head->left);	
    	}
    }

1.3中序（LeetCode94）

  • 递归：左、中、右

    1
    2
    3
    4
    5
    6
    7
    8
    void inOrder(Node* root) {
    	if (root == NULL)
    		return;
    	
    	inOrder(root->left);
    	cout << root->value;
    	inOrder(root->right);
    }

  • 迭代：利用栈特性来做

    • 一直延申指向左孩子，同时存入元素
    • 当左孩子为空，输出，同时指向右孩子
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      void inorder(Node* head)//中序遍历
      {
      	if (head == NULL)
      		return;

      	stack <Node*>q;
      	while (!q.empty() || head != NULL) {
      		if (head != NULL) {
      			q.push(head);
      			head = head->left;//如果一直不空，就一直指向左孩子 
      		}
      		else {
      			Node* tmp = q.top();
      			q.pop();
      			cout << head->value << " "; //如果为空，输出，同时指针指向右孩子
      			head = tmp->right;        
      		}
      	}
      }

1.4后序（LeetCode145）

  • 利用先序和两个栈来实现

  • 左、右、中

    • 类似前序，前序：中左右，所以先进右
    • 后序：左右中，所以先形成中右左，然后利用stack反向打印，就变成了左右中
      1
      2
      3
      4
      5
      6
      7
      8
      void afterOrder(Node* root) {
      	if (root == NULL)
      		return;

      	afterOrder(root->left);
      	afterOrder(root->right);
      	cout << root->value;
      }

  • 利用栈特性来做

    • 先实现右中左，然后反向打印。 
      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 postOrder(Node* head) {		
      	if (head == NULL)
      		return;
      	
      	stack<Node*>arr;
      	stack<Node*>q;
      	q.push(head);    //利用栈的特性，先进右孩子   
      	while (!q.empty())
      	{
      		head = q.top();
      		arr.push(head);

      		q.pop();
      		//和先序相反：先进左
      		if (head->left)q.push(head->left);
      		if (head->right)q.push(head->right);
      	}
      	while (!arr.empty()) {
      		Node* tmp = arr.top();
      		arr.pop();
      		cout << tmp->value << " ";
      	}

      }

2.剑指Offer树相关题型

J_7.重建二叉树

  • 前序遍历 preorder = [3,9,20,15,7]

  • 中序遍历 inorder = [9,3,15,20,7]

  • 解：先序定根、中序划分区间

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
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	return build(preorder, 0, inorder, 0, inorder.size() - 1);
}                          //先序定根:          中序:划分区间
TreeNode* build(vector<int>& preorder, int root, vector<int>& inorder, int start, int end) {
	if (start > end)
		return NULL;

	//先序定根,然后其左右树再根据中序确定
	TreeNode* tree = new TreeNode(preorder[root]);

	//中序定两侧子树,定位到对应root值位置
	int i = start;
	while (i < end && preorder[root] != inorder[i])
		i++;


	tree->left = build(preorder, root + 1, inorder, start, i - 1);
	tree->right = build(preorder, root + 1 + (i - 1 - start + 1), inorder, i + 1, end);

	return tree;
}

J_26.判断是不是树的子结构

  • 每个节点都有可能是节点

  • 1.判断每个节点

  • 2.然后验证每个节点

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isSubStructure(TreeNode* A, TreeNode* B) {
	if (A == NULL || B == NULL)
		return false;

	//验证当前节点  、  判断左孩子节点、  判断右孩子结点
	return dfs(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
bool dfs(TreeNode* A, TreeNode* B) {
	if (B == NULL)
		return true;
	if (A == NULL)
		return false;
	if (A->val != B->val)
		return false;
	//继续验证剩下的节点
	return dfs(A->left, B->left) && dfs(A->right, B->right);
}

J_27.二叉树的镜像

img

  • 1.递归

  • 2.或者队列层序遍历过程，交换节点实现
    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
    //递归
    TreeNode* dfs(TreeNode* root) {
    	if (root == NULL)
    		return root;

    	TreeNode* temp = root->left;
    	root->left = root->right;
    	root->right = temp;

    	dfs(root->left);
    	dfs(root->right);

    	return root;
    }
    //队列，迭代
    TreeNode* mirrorTree(TreeNode* root) {
    	queue<TreeNode*> que;
    	que.push(root);
    	while (!que.empty())
    	{
    		TreeNode* tmp = que.front();
    		que.pop();
    		if (tmp == NULL) continue;
    		swap(tmp->left, tmp->right);
    		if (tmp->left) que.push(tmp->left);
    		if (tmp->right) que.push(tmp->right);
    	}
    	return root;
    }

J_28.对称的二叉树

  • 验证每个余下的节点都需要满足，每个节点都要满足，传入左孩子节点和右孩子节点。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isSymmetric(TreeNode* root) {
	if (root == NULL)
		return true;

	return dfs(root->left, root->right);
}

bool dfs(TreeNode* left, TreeNode* right) {
	if (left == NULL && right == NULL)
		return true;
	if (left == NULL || right == NULL)
		return false;
	if (left->val != right->val)
		return false;
	return dfs(left->left, right->right) && dfs(left->right, right->left);
}

J_32-1.层序打印二叉树

  • 典型的层序遍历，按层依次打印节点value值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    vector<int> levelOrder(TreeNode* root) {
    	//利用队列层序遍历
    	if (root == NULL)
    		return {};
    	queue<TreeNode*>q;
    	q.push(root);

    	vector<int>res;
    	while (!q.empty()) {
    		int size = q.size();
    		for (int i = 0; i < size; i++) {
    			TreeNode* temp = q.front();
    			int num = temp->val;
    			res.push_back(num);
    			q.pop();

    			if (temp->left)q.push(temp->left);
    			if (temp->right)q.push(temp->right);
    		}
    	}
    	return res;
    }

J_33.二叉搜索树的后序遍历判断

  • 一个数组，判断数组是不是二叉树的后序遍历

  • 输入: [1,6,3,2,5]

  • 输出: false

img

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 verifyPostorder(vector<int>& postorder) {
	if (postorder.size() < 2)return true;

	int root = postorder.size() - 1;
	return dfs(postorder, 0, root);
}
//二叉搜索树：左<中<右
//后序遍历：左 右 中
bool dfs(vector<int>& postorder, int left, int root) {
	if (left >= root)//只剩一个节点时候，之前已经满足了搜索二叉树的条件
		return true;//所以还是满足，返回true

	int rootValue = postorder[root];

	//区分左右区间，先找左右区间的区分节点位置
	int i = left;
	while (i < root && postorder[i] < rootValue)
		i++;
	//此时i已经是第一个右节点位置
	for (int j = i; j < root; j++)
		if (postorder[j] < rootValue)return false;

	//继续验证剩下的区间
	return dfs(postorder, left, i - 1) && dfs(postorder, i, root - 1);
}

J_34.二叉树中的路径和(回溯)

  • 需要遍历到底部：每条路都是有可能的，所以用回溯

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//找到所有路
vector<vector<int>>res;
vector<vector<int>> pathSum(TreeNode* root, int sum) {
	vector<int>temp;
	dfs(root, sum, temp);
	return res;
}
void dfs(TreeNode* root, int sum, vector<int>& arr) {
	//if(root == NULL || sum < 0)
	if (root == NULL)
		return;

	arr.push_back(root->val);
	sum -= root->val;

	if (sum == 0 && root->left == NULL && root->right == NULL)
		res.push_back(arr);
	else {
		dfs(root->left, sum, arr);
		dfs(root->right, sum, arr);
	}

	arr.pop_back();
}

J_34.拓展.二叉树中的路径和

img1

1
2
3
4
5
6
7
8
bool hasPathSum(TreeNode* root, int sum) {
	if (root == NULL)
		return false;
	if (root->left == NULL && root->right == NULL )
		return sum - root->val == 0;

	return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}

J_37.序列化二叉树（先序遍历构建）

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
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

string serialize(TreeNode* root) {
	if (root == NULL)
		return "#,";

	string res = to_string(root->val) + ",";
	res += serialize(root->left);
	res += serialize(root->right);

	return res;
}

//先序
//反序列化
TreeNode* deserialize(string data) {
	//利用getline来截取string
	stringstream arr(data);
	string temp;

	queue<string>q;
	while (getline(arr, temp, ',')) {
		q.push(temp);
	}

	return dfs(q);
}
TreeNode* dfs(queue<string>&q) {
	if (q.size() == 0)
		return NULL;

	string temp = q.front();
	q.pop();
	if (temp == "#")
		return NULL;

	TreeNode* root = new TreeNode(stoi(temp));
	root->left = dfs(q);
	root->right = dfs(q);

	return root;
}

J_55-1.计算二叉树的高度

  • 递归下去

1
2
3
4
5
6
int maxDepth(TreeNode* root) {
	if (root == NULL)
		return 0;

	return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

J_55.拓展.求二叉树的最大直径

img1

  • 利用上一题的求节点的最大深度

  • 在求数深度的过程中，不单单只是MAX（left，right）+1

    • 而是比较max（res，L+R）;

  • 在求数的深度的过程中，比较maxLength

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19

    int length;
    int diameterOfBinaryTree(TreeNode* root) {
    	length = 0;
    	dfs(root);
    	return length;
    }
    int dfs(TreeNode* root) {
    	if (root == NULL)
    		return 0;
    	
    	int L = dfs(root->left);
    	int R = dfs(root->right);

    	int curlength = L + R;
    	length = max(length, curlength); //这个节点的最大值

    	return max(L, R) + 1;            //返回该子节点的最大分治
    }

J_55-2.判断是否平衡二叉树

  • 平衡二叉树：高度差小于等于1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool dfs(TreeNode* root) {
	if (root == NULL)
		return true;

	//当前节点满足
	if (abs(depth(root->left) - depth(root->right)) > 1) return false;

	//余下节点满足
	return dfs(root->left) && dfs(root->right);
}

int depth(TreeNode* root) {
	if (root == NULL)
		return 0;
	return max(depth(root->left), depth(root->right)) + 1;
}

J_68-1.二叉搜索树的最近公共祖先

  • 利用二叉搜索树的特性

  • 左 < 中 < 右
  • 利用节点的值，来进行计算，只有当的Value值一个大于，一个小于：找到节点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    	if (root == NULL)
    		return NULL;

    	if (root->val > p->val && root->val > q->val)
    		return lowestCommonAncestor(root->left, p, q);

    	if (root->val < p->val &&root->val < q->val)
    		return lowestCommonAncestor(root->right, p, q);

    	return root;
    }

J_68-2.二叉树的最近公共祖先

  • 依次往下遍历节点

  • 如果找到了：q、p返回

  • 否则：继续往下遍历，查看左树和右树的查询结果。
    img
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
	if (root == NULL)
		return NULL;

	//该节点是val,直接返回
	if (root == p || root == q)
		return root;
	else 
	{//该节点不是val继续判断左、右
		TreeNode* L = lowestCommonAncestor(root->left, p, q);
		TreeNode* R = lowestCommonAncestor(root->right, p, q);

		if (L && R)
			return root;
		if (L == NULL && R != NULL)
			return R;
		if (R == NULL && L != NULL)
			return L;

		return NULL;
	}
	return NULL;
}

222.完全二叉树的节点数

  • 方法一:递归
  • 方法二:利用性质logn * logn
  • 方法三:利用二分法计算
1
2
3
4
5
6
7
//方法一:递归
 int countNodes(TreeNode* root) {
     //递归
     if(root == NULL)
         return 0;
     return countNodes(root->right) + countNodes(root->left) + 1;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//方法二:利用性质logn * logn
 int countNodes(TreeNode* root) {
     if(root == NULL)
         return 0;

     int lLevel = countLevel(root->left);
     int rLevel = countLevel(root->right);

     //右子树满
     if(lLevel != rLevel)
         return countNodes(root->left) + (1<<rLevel);
     else//左子树满
         return countNodes(root->right) + (1<<lLevel);
 }
 
 int countLevel(TreeNode* root) {
	int Level = 0;
	while (root) {
		root = root->left;
		Level++;
	}
	return Level;
}
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
//方法三:利用二分法计算
int countNodes(TreeNode* root) {
	TreeNode* cur = root;
	int level = 1;
	int h = countLevel(root);
	//res是做后一层的节点个数
	int res = 0;
	while (cur) {
		TreeNode* temp = cur->right;
		//左==右:左子树满,接下来只要考虑右子树
		if (level + countLevel(temp) == h && temp) {
			cur = cur->right;
			res += pow(2, h - level - 1);
			level += 1;
		}
		else {
			cur = cur->left;
			level += 1;
		}
	}
    //结果等于最后一层 + 前面N层
	return res + pow(2, h - 1);
}

int countLevel(TreeNode* root) {
	int Level = 0;
	while (root) {
		root = root->left;
		Level++;
	}
	return Level;
}

二分

  • 头文件：algorithm

  • lower_bound( begin,end,num )
    • 查找第一个大于或等于num的数字—— >=num
  • upper_bound( begin,end,num )
    • 查找第一个大于num的数字 —— >num

  • auto iter = upper_bound(A.begin(), A.end(), B[i]);

  • 返回：迭代器
  • ans.push_back(* iter);
    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
    //大于或等于target的第一个数
    int lower_bound(vector<int>& nums, int target) {
    	int L = 0;
    	int R = nums.size();
    	while (L < R) {
    		int mid = (L + R) >> 1;
    		if (nums[mid] < target)
    			L = mid + 1;
    		else
    			R = mid;
    	}
    	return L;
    }

    //大于target的第一个数
    int upper_bound(vector<int>& nums, int target) {
    	int L = 0;
    	int R = nums.size();
    	while (L < R) {
    		int mid = (L + R) >> 1;
    		if (nums[mid] <= target)
    			L = mid + 1;
    		else
    			R = mid;
    	}
    	return L;
    }

33.搜索旋转排序数组

  • 假设按照升序排序的数组在预先未知的某个点上进行了旋转。

  • ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

  • 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

  • 你可以假设数组中不存在重复的元素。

  • 你的算法时间复杂度必须是 O(log n) 级别。

  • 输入: nums = [4,5,6,7,0,1,2], target = 0

  • 输出: 4

  • 输入: nums = [4,5,6,7,0,1,2], target = 3

  • 输出: -1

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
int search(vector<int>& nums, int target) {
	if (nums.size() == 0) return -1;
	int n = nums.size() - 1;
	if (n == 0) return nums[0] == target ? 0 : -1;

	int l = 0, r = n;
	while (l <= r) {
		int mid = l + r >> 1;
		if (nums[mid] == target)return mid;
		//我们只选择有序的半部分来考虑，同时这里mid已经判断了，所以下面直接选择mid+1或mid-1

				//左侧有序
		if (nums[l] <= nums[mid]) {

			if (nums[l] <= target && target <= nums[mid]) {
				r = mid - 1;
			}
			else {
				l = mid + 1;
			}
		}
		else // 右侧有序
		{
			if (nums[mid] <= target && target <= nums[r]) {
				l = mid + 1;
			}
			else {
				r = mid - 1;
			}
		}
	}
	return -1;
}

34. 在排序数组中查找元素的第一个和最后一个位置

  • 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

  • 你的算法时间复杂度必须是 O(log n) 级别。

  • 如果数组中不存在目标值，返回 [-1, -1]。

  • 输入: nums = [5,7,7,8,8,10], target = 8

  • 输出: [3,4]

  • 输入: nums = [5,7,7,8,8,10], target = 6

  • 输出: [-1,-1]

    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
    //大于等于target的第一个数
    int lower_bound(vector<int>& nums, int target) {
    	int L = 0;
    	int R = nums.size();
    	while (L < R) {
    		int mid = (L + R) >> 1;
    		if (nums[mid] < target)
    			L = mid + 1;
    		else
    			R = mid;
    	}
    	return L;
    }

    //大于target的第一个数
    int upper_bound(vector<int>& nums, int target) {
    	int L = 0;
    	int R = nums.size();
    	while (L < R) {
    		int mid = (L + R) >> 1;
    		if (nums[mid] <= target)
    			L = mid + 1;
    		else
    			R = mid;
    	}
    	return L;
    }

    vector<int> searchRange(vector<int>& nums, int target) {

    	int L = lower_bound(nums, target);
    	int R = upper_bound(nums, target);

    	//说明不存在target
    	if (L == R)
    		return vector<int>{-1, -1};

    	return vector<int>{L, R - 1};
    }

4.重要：两个正序数组，第K小的数

img

  • 采用二分的方法

  • 1.先取数组中各个中间的数，小的部分舍去这个区间。

  • 2.第K小的数，随之减去舍去这个区间的大小。

    • 1.当一个区间为0，再剩下的数组中
    • 2.当K=1，说明还剩下一个，min(top1,top2).

  • 为了保证当一个区间为0，直接返回：我们永远让上一个数组的容量为小，再进行判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int find(vector<int>arr1, int begin1, int end1, vector<int>arr2, int begin2, int end2, int k) {
	//数组还存在的空间
	int len1 = end1 - begin1 + 1;
	int len2 = end2 - begin2 + 1;
	//保证前面的数组所剩元数少！！
	if (len1 > len2)
		return find(arr2, begin2, end2, arr1, begin1, end1, k);
	if (len1 == 0)
		return arr2[begin2 + k - 1];
	if (k == 1)
		return min(arr1[begin1], arr2[begin2]);

	//将K进行二分,最新的元素下标,保证不越界
	int deleteLen = k / 2;
	int i = begin1 + min(len1, deleteLen) - 1;
	int j = begin2 + min(len2, deleteLen) - 1;

	//哪边小,哪边做出调整
	if (arr1[i] > arr2[j])                  //小的部分去除————K去掉长度
		return find(arr1, begin1, end1, arr2, j + 1, end2, k - (j - begin2 + 1));
	else                 //小的部分去除
		return find(arr1, i + 1, end1, arr2, begin2, end2, k - (i - begin1 + 1));
}

一个数的平方根 / pow(x,n)的实现

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
int sqrt(int x) {
	if (x < 2)
		return x;

	//二分方法
	int L = 0;
	int R = x - 1;
	while (L < R) {
		//向上取整
		int mid = L + R + 1 >> 1;
		if (mid <= x / mid)
			L = mid;
		else
			R = mid - 1;
	}
	return L;
}

double myPow(double x, int n) {
	if (n == 0) return 1;
	if (n == 1) return x;
	if (n == -1) return 1 / x;
	double half = myPow(x, n / 2);
	double add = myPow(x, n % 2);

	return half * half*add;
}
文章作者: Inter
文章链接: https://zuizichuan.cn/2020/08/08/LeetCode-%E6%A0%91%E3%80%81%E9%93%BE%E8%A1%A8%E4%B8%93%E9%A2%98/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Zichuan365' Blog！