一、二叉树与递归
二叉树与递归有着千丝万缕的联系，二叉树在定义时就使用了递归的概念：一棵二叉树可能是空树，如果不是空树，那么它的左右子树都是二叉树。我们一般这样定义二叉树的节点TreeNode，它包含三个成员：该节点的值，该节点的左子树和该节点的右子树。TreeNode的构造函数在新建节点时会将它的左右子树都赋值为空。
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
二叉树与线性数据结构不同的是，它无法像数组或者链表一样使用一个循环就可以从头到尾遍历所有的数据。二叉树是发散的，你不知道他的左子树或是右子树延伸了多少个节点，你只有在遍历完一棵二叉树时你才知道它的结构。那么该怎么遍历二叉树呢？
首先，二叉树的遍历分为深度优先遍历和广度优先遍历，深度优先遍历分为先序、中序和后序。以先序遍历为例，程序会先访问root节点，然后依次遍历root的左子树和右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。
前序遍历很容易让人想到递归，它会访问根节点之后再递归地访问左子树，之后再递归地访问右子树。根据这样的思路可以写出前序遍历的递归代码，递归最重要的是返回条件，这里的返回条件是二叉树为空。
void preOrder(TreeNode* root) {
if (root == NULL) return; // 当前二叉树为空，则表示该分支已经访问结束
cout << root->value;
preOrder(root->left); // 递归访问左子树
preOrder(root->right); // 递归访问右子树
}
了解前序遍历之后，也就能很轻易地写出中序和后序的代码，这里不再赘述。
二、二叉树递归实战
1. 二叉树的深度
Leetcode地址：104. 二叉树的最大深度
这道题要求的是二叉树的深度，或者说高度，也就是求二叉树根节点到最远的叶节点所经过的节点数。下方的二叉树深度为3，因为从根节点3到叶节点15和到叶节点7都要经过3个节点。
3
/ \
9 20
/ \
15 7
很显然，一棵二叉树的高度 = max(左子树高度, 右子树高度) + 1，上方二叉树的左子树高度为1，右子树高度为2，那么很容易得出整个二叉树高度为3。而左右子树的高度又可以递归求出，只需在二叉树为空时返回高度0即可。
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
2. 翻转二叉树
Leetcode地址：226. 翻转二叉树
例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
可以看到，翻转二叉树时会将所有节点的左右子树都进行一次翻转。相对于根节点，节点2和节点7的位置进行了对调，而相对于节点2，节点3和节点1的位置进行了对调……因此可以通过递归来对每个节点的左右子树进行对调，在遇到空树时退出递归。
TreeNode* invertTree(TreeNode* root) {
invert(root);
return root;
}
void invert(TreeNode* root) {
if (root == NULL) return;
// 对调左右子树
TreeNode* tmp = root->left;
root->left = root->right;
root->right = tmp;
// 递归左右子树
invert(root->left);
invert(root->right);
}
3. 相同的树
Leetcode地址：100. 相同的树
该题要判断两个二叉树是否相同。只有两个二叉树的结构相同并且每个节点上的值相同，它们才是相同的树。
既然要判断所有的节点，那么很显然可以用递归求解：假设当前有两个二叉树root1和root2，如果其中一个为空而另一个不为空，返回false；如果两个都为空，返回true；如果都不为空，则判断这两个节点的值是否相同，不同则返回false，相同的话则再判断它们的左右子树是否相同。
bool isSameTree(TreeNode* p, 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;
}
}
4. 合并二叉树
Leetcode地址：617. 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
例：
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
这道题很明显也是一道递归题，我们需要同时遍历两棵树，如果当前节点都不为空，则将两个值相加形成新的节点；如果其中一个为空，则以该节点的值新建节点；如果都为空，则返回空。
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 != NULL && t2 != NULL) { // 都不为空，则将两个节点的值相加
TreeNode* node = new TreeNode(t1->val + t2->val);
node->left = mergeTrees(t1->left, t2->left);
node->right = mergeTrees(t1->right, t2->right);
return node;
} else if (t1 != NULL) { // t1不为空, t2为空
TreeNode* node = new TreeNode(t1->val);
node->left = mergeTrees(t1->left, NULL);
node->right = mergeTrees(t1->right, NULL);
return node;
} else if (t2 != NULL) { // t1为空, t2不为空
TreeNode* node = new TreeNode(t2->val);
node->left = mergeTrees(t2->left, NULL);
node->right = mergeTrees(t2->right, NULL);
return node;
} else {
return NULL;
}
}
5. 从前序与中序遍历序列构造二叉树
Leetcode地址：105. 从前序与中序遍历序列构造二叉树
例：
前序遍历preorder = [3, 9, 20, 15, 7]
中序遍历 inorder = [9, 3, 15, 20, 7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
根据上面的例子，前序遍历的第一个节点3就是二叉树的根节点，在中序遍历中找到3，中序遍历中，3之前的就是左子树的节点，3之后的就是右子树的节点。那么左子树的前序遍历就是[9]，中序遍历也是[9]，所以左子树只有一个值为9的节点。右子树的前序遍历为[20, 15, 7]，中序遍历为[15, 20, 7]，那么右子树的根节点就是15，以此类推……
很容易发现这也是一个递归的程序：前序遍历的第一个值就是根节点root，然后在中序遍历中找到root。那么在中序遍历中root前的n个值就是左子树的中序遍历，root后的m个值就是右子树的中序遍历。前序遍历中root之后的n个值就是左子树的前序遍历，剩下的m个值就是右子树的前序遍历。
这样就得到了左右子树的前序遍历和中序遍历，即可递归得到整个二叉树。
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.size() == 0) return NULL;
int index = preorder.size() - 1;
return build(preorder, inorder, 0, index, 0, index);
}
// s1 和 e1 为前序遍历的起点和终点, s2 和 e2 为中序遍历的起点和终点
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int s1, int e1, int s2, int e2) {
if (s1 == e1) {
TreeNode* node = new TreeNode(preorder[s1]);
return node;
}
if (s1 > e1 && s2 > e2) {
return NULL;
}
// 新建根节点
TreeNode* root = new TreeNode(preorder[s1]);
// 找到中间节点
int middle2;
for (int i = s2; i <= e2; ++i) {
if (preorder[s1] == inorder[i]) {
middle2 = i;
break;
}
}
if (middle2 == s2) {
root->right = build(preorder, inorder, s1 + (middle2 - s2 + 1), e1, middle2 + 1, e2);
} else if (middle2 == e2) {
root->left = build(preorder, inorder, s1 + 1, s1 + (middle2 - s2), s2, middle2 - 1);
} else {
// 递归调用
root->left = build(preorder, inorder, s1 + 1, s1 + (middle2 - s2), s2, middle2 - 1);
root->right = build(preorder, inorder, s1 + (middle2 - s2 + 1), e1, middle2 + 1, e2);
}
return root;
}
理解该题之后还可以尝试一下106. 从中序与后序遍历序列构造二叉树
三、二叉搜索树
二叉搜索树(Binary Search Tree)也叫二叉排序树，简称为BST。它具有这样的性质：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。(仔细观察可以发现，二叉搜索树的中序遍历可以得到一个有序数组)。
在二叉搜索树中查找某个值的操作类似有序数组中的二分查找，时间复杂度都是O(logn)，但是在BST中插入新的值比在有序数组中要快得多，因为在BST中插入新的值，只需使用O(logn)的时间找到插入点然后插入即可；而在有序数组中，找到插入点之后需要将该点之后的元素都向后移动一位，移动多个元素的操作非常消耗时间。
以下图的二叉搜索树为例，在其中进行查找和插入的操作。
① 查找元素7：从根节点开始查找，根节点为15，而要查找的值7小于15，则去节点15的左子树进行查找；查找到节点6时，发现要查找的值7大于6，则去节点6的右子树进行查找；查找到节点7，找到结果，退出。
② 插入元素19：开始时与查找过程类似，直到找到节点20，发现19比20小且20的左子树为空，则将19插入到节点20的左子树。
有时二叉搜索树的插入顺序不理想，那么会得到一棵偏向一边的BST，这时的BST就退化成了链表。如下所示，对于这几个数据，我们期望的BST肯定是左边这样的，但是如果我们按1->2->3->4->5->6这样的顺序插入，就会得到右边这样的BST。因此如果给定一个有序数组来构建二叉搜索树，需要挑选中间的值来作为根节点。
四、二叉搜索树实战
1. 二叉搜索树中的搜索
Leetcode地址：700. 二叉搜索树中的搜索
这道题思路很清楚：假设从节点root开始查找value，如果value == root->val，则找到结果；如果value < root->val，则移动到root->left进行查找；否则移动到root->right进行查找。如果查找完整棵树还没有发现，就返回空。
TreeNode* searchBST(TreeNode* root, int val) {
if (root == NULL) return NULL;
if (root->val == val) return root;
else if (val < root->val) return searchBST(root->left, val);
else return searchBST(root->right, val);
}
2. 二叉搜索树中的插入
Leetcode地址：701. 二叉搜索树中的插入操作
在对二叉树进行插入操作之前需要先找到插入点，而寻找插入点与上一题的搜索类似，当找到为空的地方时就可以将当前节点插入。
TreeNode* insertIntoBST(TreeNode* root, int val) {
TreeNode* cur = new TreeNode(val);
insert(root, cur);
return root;
}
void insert(TreeNode* &node, TreeNode* cur) {
if (node == NULL) { // 找到为空的分支, 即可插入当前节点
node = cur;
return;
}
if (cur->val < node->val) {
insert(node->left, cur);
} else if (cur->val > node->val) {
insert(node->right, cur);
} else {
TreeNode* temp = node->left;
node->left = cur;
cur->left = temp;
}
}
3. 将有序数组转换为二叉搜索树
Leetcode地址：108. 将有序数组转换为二叉搜索树
题目要求将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。既然要求BST高度平衡，那么肯定要将数组中间的值作为根节点，而左子树的根节点则是数组左半部分的中间值，右子树的根节点是数组右半部分的中间值……依次递归
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.size() == 0) return NULL; // 如果数组为空, 返回空树
TreeNode* root;
generateBST(nums, root, 0, nums.size() - 1);
return root;
}
void generateBST(vector<int>& nums, TreeNode* &ptr, int start, int end) {
int middle = (start + end) / 2;
ptr = new TreeNode(nums[middle]); // 用数组中间值新建一个节点
if (start <= middle - 1) { // 如果左边还有数据
generateBST(nums, ptr->left, start, middle - 1);
}
if (middle + 1 <= end) { // 如果右边还有数据
generateBST(nums, ptr->right, middle + 1, end);
}
}
上述代码用到了C++中的引用，如果不习惯这种调用方式，可以这么写。
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.size() == 0) return NULL;
return build(nums, 0, nums.size() - 1);
}
// 构建完一个节点之后直接返回
TreeNode* build(vector<int>& nums, int start, int end) {
if (start > end) return NULL;
int mid = (start + end) / 2;
TreeNode* node = new TreeNode(nums[mid]);
node->left = build(nums, start, mid - 1);
node->right = build(nums, mid + 1, end);
return node;
}
