下面是DFS Medium级别题目的后5道，列表目录：
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
将一个升序数组转换成一个高度平衡的二分查找树BST，即AVL树，递归方法很easy.
TreeNode *BST(vector<int> &num, int start, int end)
{
if (start > end)
{
return NULL;
}
int mid = (start + end) / 2;
TreeNode *root = new TreeNode(num[mid]);
root->left = BST(num, start, mid - 1);
root->right = BST(num, mid + 1, end);
}
TreeNode *sortedArrayToBST(vector<int> &num)
{
if (num.size() < 1)
{
return NULL;
}
return BST(num, 0, num.size() - 1);
}Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
将有序链表转换成有序数组，再按照Convert Sorted Array to Binary Search Tree方法来建BST树。
缺点就是消耗了O(n)的额外空间，下策。
TreeNode *buildTree(vector<int> &arr, int si, int ei)
{
if (si > ei)
{
return NULL;
}
else
{
int mi = (si + ei) / 2;
TreeNode *node = new TreeNode(arr[mi]);
node->left = buildTree(arr, si, mi - 1);
node->right = buildTree(arr, mi + 1, ei);
}
}
TreeNode *sortedListToBST(ListNode *head)
{
vector<int> arr;
for (ListNode*p = head; p; p = p->next)
{
arr.push_back(p->val);
}
TreeNode *root = buildTree(arr, 0, arr.size() - 1);
return root;
}我们多花点时间来查找链表的中间结点吧，时间复杂度还是O(n)，空间复杂度降到O(1).
TreeNode *buildTree(ListNode *head, int len)
{
if (len < 1)
{
return NULL;
}
else
{
int mid = 0;
ListNode *p;
for (p = head; mid < len / 2; p = p->next, mid++);
TreeNode *node = new TreeNode(p->val);
node->left = buildTree(head, mid);
node->right = buildTree(p->next, len - mid - 1);
}
}
TreeNode *sortedListToBST(ListNode *head)
{
int n = 0;
for (ListNode*p = head; p; p = p->next, n++);
return buildTree(head, n);
}Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree.
根据先根遍历可以确定根结点，有了根结点，就可以分割中根遍历序列，左边是左子树，右边是右子树。所以题目中的假设前提很重要，没有重复的结点！
TreeNode *build(vector<int> &preorder, int psi, int pei,
vector<int> &inorder, int isi, int iei)
{
if (psi > pei || isi > iei)
{
return NULL;
}
int imi = isi;
for (imi; imi <= iei && preorder[psi] != inorder[imi]; imi++);
assert(imi <= iei);
int psep = imi - isi + psi;
TreeNode *root = new TreeNode(preorder[psi]);
root->left = build(preorder, psi + 1, psep, inorder, isi, imi - 1);
root->right = build(preorder, psep + 1, pei, inorder, imi + 1, iei);
return root;
}
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
{
if (preorder.size() < 1)
{
return NULL;
}
return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree.
和前一题目类似，后根遍历序列用来确定根结点，由这个根结点划分中根遍历序列，从而确立左右子树。
TreeNode *build(vector<int> &inorder, int isi, int iei,
vector<int> &postorder, int psi, int pei)
{
if (psi > pei || isi > iei)
{
return NULL;
}
int imi = isi;
for (imi; imi <= iei && postorder[pei] != inorder[imi]; imi++);
assert(imi <= iei);
int psep = imi - isi + psi - 1;
TreeNode *root = new TreeNode(postorder[pei]);
root->left = build(inorder, isi, imi - 1, postorder, psi, psep);
root->right = build(inorder, imi + 1, iei, postorder, psep + 1, pei - 1);
return root;
}
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
{
if (inorder.size() < 1)
{
return NULL;
}
return build(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ's undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
邻接表法表示的图结构，每个node的标签是唯一的。主要的问题是避免重复clone结点。
clone过程分两步
struct UndirectedGraphNode {
int label;
vector<UndirectedGraphNode *> neighbors;
UndirectedGraphNode(int x) : label(x) {};
};
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
//1. 遍历所有顶点，并创建新节点
queue<UndirectedGraphNode*> gqueue;
map<int, UndirectedGraphNode*> gmap;
UndirectedGraphNode *p;
if (node)
{
gqueue.push(node);
}
while (!gqueue.empty())
{
p = gqueue.front();
gqueue.pop();
if (gmap.find(p->label) != gmap.end())
{//already exists
continue;
}
gmap[p->label] = new UndirectedGraphNode(p->label);
for (int i = 0; i < p->neighbors.size(); i++)
{
gqueue.push(p->neighbors[i]);
}
}
//2. 将gmap中的节点连接起来
set<int> visited;
if (node)
{
gqueue.push(node);
}
while (!gqueue.empty())
{
p = gqueue.front();
gqueue.pop();
if (visited.find(p->label) != visited.end())
{//already visited
continue;
}
visited.insert(p->label);
for (int i = 0; i < p->neighbors.size(); i++)
{
gqueue.push(p->neighbors[i]);
gmap[p->label]->neighbors.push_back(gmap[p->neighbors[i]->label]);
}
}
//
if (node)
{
return gmap[node->label];
}
return node;
}
};到此，LeetCode Esay和Medium级别的DFS类型题目已经完了，还剩下3道Hard。