1. 链表
链表是最基本的数据结构，面试官也常常用链表来考察面试者的基本能力，而且链表相关的操作相对而言比较简单，也适合考察写代码的能力。链表的操作也离不开指针，指针又很容易导致出错。综合多方面的原因，链表题目在面试中占据着很重要的地位。
链表问题中的一个重要的方法叫双指针法。定义两个指针，一个叫慢指针，另一个叫快指针。通常慢指针每次向前移动一个节点，而快指针每次向前移动若干个节点。这个方法通常用于寻找链表中特定的位置。比如找到链表的中点，可以让快指针每次移动两个节点。这样当快指针到达链表末尾时，慢指针刚好在链表中间的位置。
链表结点声明如下：
struct ListNode
{
int value;
ListNode * next;
ListNode(int x) : value(x), next(NULL) {}
};
1.1 求单链表中结点的个数
这是最最基本的了，应该能够迅速写出正确的代码，注意检查链表是否为空。时间复杂度为O（n）。
int GetListLenght(ListNode* head)
{
if(head == NULL) return 0;
ListNode* current = head;
int len = 0;
while(current != NULL)
{
len++;
current = current->next;
}
return len;
}
1.2 将单链表反转
从头到尾遍历原链表，每遍历一个结点，将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O（n）。
ListNode* ReverseList(ListNode* head)
{
if(head == NULL || head->next == NULL) return head;
ListNode* reverseHead = NULL;
ListNode* current = head;
while(current != NULL)
{
ListNode* temp = current;
current = current->next;
temp->next = reverseHead;
reverseHead = temp;
}
return reverseHead;
}
1.3 查找单链表中的倒数第K个结点（k>0）
使用两个指针，先让前面的指针走到正向第k个结点，这样前后两个指针的距离差是k-1，之后前后两个指针一起向前走，前面的指针走到最后一个结点时，后面指针所指结点就是倒数第k个结点。
ListNode * RGetKthNode(ListNode * head, unsigned int k)
{
if(head == NULL) return NULL;
ListNode* aHead = head, behind = head;
while(k>1)
{
if(aHead == NULL) return NULL;
aHead = aHead->next;
k--;
}
while(aHead->next != NULL)
{
behind = behind->next;
aHead = aHead->next;
}
return behind;
}
1.4 判断一个单链表中是否有环
如果一个链表中有环，也就是说用一个指针去遍历，是永远走不到头的。因此，我们可以用两个指针去遍历，一个指针一次走两步，一个指针一次走一步，如果有环，两个指针肯定会在环中相遇。时间复杂度为O（n）。
bool HasCycle(ListNode* head)
{
ListNode* fast = head,* slow = head;
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow) return true;
}
return false;
}
1.5 判断一个单链表中是否有环，如果存在，求进入环中的第一个节点
这题不光要求出是否有环，而且还需要得到这个环开始的节点。譬如下面这个，起点就是n2。
n6-----------n5
| |
n1------n2----n3----n4|
我们仍然可以使用两个指针fast和slow，fast走两步，slow走一步，判断是否有环，当有环重合之后，譬如上面在n5重合了，那么如何得到n2呢？
首先我们知道，fast每次比slow多走一步，所以重合的时候，fast移动的距离是slot的两倍，我们假设n1到n2距离为a，n2到n5距离为b，n5到n2距离为c，fast走动距离为a+ b+c+b，而slow为 a+b，有方程a+b+c+b=2x(a+b)，可以知道a=c，所以我们只需要在重合之后，一个指针从n1，而另一个指针从n5，都每次走一步，那么就可以在n2重合了。
ListNode* detectCycle(ListNode* head)
{
ListNode *slow = head, *fast = head;
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
ListNode* slow2 = head;
while(slow2 != slow)
{
slow2 = slow2->next;
slow = slow->next;
}
return slow2;
}
}
return NULL;
}
1.6 合并两个排好序的链表
利用附加头结点简化操作
ListNode* MergeTowList(ListNode* head1, ListNode* head2)
{
ListNode* dummy(0);
ListNode* temp = &dummy;
while(head1 != NULL && head2 != NULL)
{
int val1 = head1->value;
int val2 = head2->value;
if(val1 < val2)
{
temp->next = head1;
temp = head1;
head1 = head1->next;
}
else
{
temp->next = head2;
temp = head2;
head2 = head2->next;
}
}
if(head1 != NULL) temp->next = head1;
else if(head2 != NULL) temp->next = head2;
return dummy.next;
}
1.7 去除有序链表中的重复元素
ListNode *deleteDuplicates(ListNode *head) {
if (head == nullptr) return nullptr;
for (ListNode *prev = head, *cur = head->next; cur; cur = prev->next) {
if (prev->val == cur->val) {
prev->next = cur->next;
delete cur;
}
else {
prev = cur;
}
}
return head;
}
1. 二叉树
树是一种比较重要的数据结构，尤其是二叉树。二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树是递归定义的，因此，与二叉树有关的题目基本都可以用递归思想解决，当然有些题目非递归解法也应该掌握，如非递归遍历节点等等。
二叉树节点定义如下：
struct BinaryTreeNode
{
int value;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int x) : value(x), left(NULL), right(NULL) {}
};
2.1 求二叉树中的结点个数
递归解法：
- 如果二叉树为空，节点个数为0
- 如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
int GetNodeNumber(BinaryTreeNode* root)
{
if(root == NULL) return 0;
return GetNodeNumber(root->left) + GetNodeNumber(root->right) + 1;
}
2.2 求二叉树的深度
递归解法：
- 如果二叉树为空，二叉树的深度为0
- 如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1
int GetDeepth(BinaryTreeNode* root)
{
if(root == NULL) return 0;
int depthLeft = GetDeepth(root->left);
int depthRight = GetDeepth(root->right);
return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);
}
2.3 前序遍历，中序遍历，后序遍历
前序遍历递归解法：如果二叉树为空，空操作；如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树。中序遍历递归解法：如果二叉树为空，空操作；如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树。后序遍历递归解法：如果二叉树为空，空操作；如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点。
void preOrderTraverse(BinaryTreeNode* root)
{
if(root == NULL) return;
visit(root);
PreOrderTraverse(root->left); // 前序遍历左子树
PreOrderTraverse(root->right); // 前序遍历右子树
}
void InOrderTraverse(BinaryTreeNode* root)
{
if(root == NULL) return;
InOrderTraverse(root->left); // 中序遍历左子树
visit(root); // 访问根节点
InOrderTraverse(root->right); // 中序遍历右子树
}
void PostOrderTraverse(BinaryTreeNode * root)
{
if(root == NULL) return;
PostOrderTraverse(root->left); // 后序遍历左子树
PostOrderTraverse(root->right); // 后序遍历右子树
Visit(root); // 访问根节点
}
2.4 层次遍历
相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。
void LevelTraverse(BinaryTreeNode* root)
{
if(root == NULL) return ;
queue<BinaryTreeNode*> que;
que.push(root);
while(!que.empty())
{
BinaryTreeNode* tempNode = que.front();
que.pop();
visit(tempNode);
if(root->left != NULL) que.push(tempNode->left);
if(root->right != NULL) que.push(tempNode->right);
}
return ;
}
2.5 求二叉树第K层的节点个数
递归解法：
- 如果二叉树为空或者k<1返回0
- 如果二叉树不为空并且k==1，返回1
- 如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和
int GetNodeNumKthLevel(BinaryTreeNode* root, int k)
{
if(root == NULL || k<1) return 0;
if(k == 1) return 1;
int numLeft = GetNodeNumKthLevel(root->left, k-1);
int numRight = GetNodeNumKthLevel(root->right,k-1);
return numLeft + numRight;
}
2.6 求二叉树中叶子节点的个数
递归解法：
- 如果二叉树为空，返回0；
- 如果二叉树不为空且左右子树为空，返回1；
- 如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数。
int GetLeafNodeNum(BinaryTreeNode * root)
{
if(root == NULL) return 0;
if(root->left == NULL && root->right == NULL) return 1;
int numLeft = GetLeafNodeNum(root->left); // 左子树中叶节点的个数
int numRight = GetLeafNodeNum(root->right); // 右子树中叶节点的个数
return (numLeft + numRight);
}
2.7 判断两棵二叉树是否结构相同
不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。递归解法如下：
- 如果两棵二叉树都为空，返回真
- 如果两棵二叉树一棵为空，另一棵不为空，返回假
- 如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假
bool StructureCmp(BinaryTreeNode * root1, BinaryTreeNode * root2)
{
if(root1 == NULL && root2 == NULL) // 都为空，返回真
return true;
else if(root1 == NULL || root2 == NULL) // 只有一个为空，返回假
return false;
bool resultLeft = StructureCmp(root1->left, root2->left); // 比较对应左子树
bool resultRight = StructureCmp(root1->right, root2->right); // 比较对应右子树
return (resultLeft && resultRight);
}
2.8 判断二叉树是不是平衡二叉树
平衡二叉树：
递归解法：
- 如果二叉树为空，返回真
- 如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假
bool IsAVL(BinaryTreeNode * root, int & height)
{
if(root == NULL) // 空树，返回真
{
height = 0;
return true;
}
int heightLeft;
bool resultLeft = IsAVL(root->left, heightLeft);
int heightRight;
bool resultRight = IsAVL(root->right, heightRight);
// 左子树和右子树都是AVL，并且高度相差不大于1，返回真
if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1)
{
height = max(heightLeft, heightRight) + 1;
return true;
}
else
{
height = max(heightLeft, heightRight) + 1;
return false;
}
}
2.9 求二叉树的镜像
递归解法：
- 如果二叉树为空，返回空
- 如果二叉树不为空，求左子树和右子树的镜像，然后交换左子树和右子树
BinaryTreeNode* Mirror(BinaryTreeNode* root)
{
if(root == NULL) return NULL;
BinaryTreeNode* mLeft = Mirror(root->left); // 求左子树镜像
BinaryTreeNode* mRight = Mirror(root->right); // 求右子树镜像
// 交换左子树和右子树
root->left = mRight;
root->right = mLeft;
return root;
}
2.10 递归的遍历算法
//利用栈进行递归前序遍历
void PreorderTraversal(BinaryTreeNode* root)
{
stack<const BinaryTreeNode*> s;
if(root != NULL) s.push(root);
while(!s.empty())
{
const BinaryTreeNode* temp = s.top();
s.pop();
visit(temp);
if(temp->right != NULL) s.push(temp->right);
if(temp->left != NULL) s.push(temp->left);
}
}
void InOrderTraversal(BinaryTreeNode* root)
{
stack<const BinaryTreeNode*> s;
const BinaryTreeNode* temp = root;
while(!s.empty() || temp !=NULL)
{
if(temp != NULL){
s.push(temp);
temp = temp->left;
}
else{
temp = s.top();
s.pop();
visit(temp);
temp = temp->right;
}
}
}
void PostOrderTraversal(BinaryTreeNode* root)
{
stack<const BinaryTreeNode*> s;
const BinaryTreeNode* temp = root, * pre = NULL;
do{
while(temp != NULL){
s.push(temp);
temp = temp->left;
}
pre = NULL;
while(!s.empty()){
temp = s.top();
s.pop();
//如果该结点的右子节点不存在或已被访问，就访问它
if(temp->right == pre){
visit(temp);
pre = temp;
}
else{
s.push(temp);
temp = temp->right;
break;
}
}
}while(!s.empty());
}
2.11 判断是否存在一条从root到其中一个叶子节点的路径的和等于给定的值
直接使用深度优先遍历求解
bool DFS(int target, int sum, BinaryTreeNode* root)
{
if(root == NULL) return false;
sum += root->value;
if(root->left == NULL && root->right == NULL)
{
if(sum == target) return true;
else return false;
}
bool leftPart = DFS(target,sum,root->left);
bool rightPart = DFS(target,sum,root->right);
return leftPart || rightPart;
}
bool hasPathSum(BinaryTreeNode* root,int sum)
{
if(root == NULL) return false;
return DFS(sum,0,root);
}
