一炫彩、二叉樹與遞歸
二叉樹與遞歸有著千絲萬縷的聯(lián)系匾七，二叉樹在定義時就使用了遞歸的概念：一棵二叉樹可能是空樹，如果不是空樹江兢，那么它的左右子樹都是二叉樹昨忆。我們一般這樣定義二叉樹的節(jié)點TreeNode，它包含三個成員：該節(jié)點的值杉允，該節(jié)點的左子樹和該節(jié)點的右子樹邑贴。TreeNode的構(gòu)造函數(shù)在新建節(jié)點時會將它的左右子樹都賦值為空。
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
二叉樹與線性數(shù)據(jù)結(jié)構(gòu)不同的是叔磷，它無法像數(shù)組或者鏈表一樣使用一個循環(huán)就可以從頭到尾遍歷所有的數(shù)據(jù)拢驾。二叉樹是發(fā)散的，你不知道他的左子樹或是右子樹延伸了多少個節(jié)點世澜，你只有在遍歷完一棵二叉樹時你才知道它的結(jié)構(gòu)独旷。那么該怎么遍歷二叉樹呢？
首先寥裂，二叉樹的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷，深度優(yōu)先遍歷分為先序案疲、中序和后序封恰。以先序遍歷為例，程序會先訪問root節(jié)點褐啡，然后依次遍歷root的左子樹和右子樹诺舔。在遍歷左、右子樹時备畦，仍然先訪問根結(jié)點低飒，然后遍歷左子樹，最后遍歷右子樹懂盐，如果二叉樹為空則返回褥赊。
前序遍歷很容易讓人想到遞歸，它會訪問根節(jié)點之后再遞歸地訪問左子樹莉恼，之后再遞歸地訪問右子樹拌喉。根據(jù)這樣的思路可以寫出前序遍歷的遞歸代碼，遞歸最重要的是返回條件俐银，這里的返回條件是二叉樹為空尿背。
void preOrder(TreeNode* root) {
if (root == NULL) return; // 當(dāng)前二叉樹為空，則表示該分支已經(jīng)訪問結(jié)束
cout << root->value;
preOrder(root->left); // 遞歸訪問左子樹
preOrder(root->right); // 遞歸訪問右子樹
}
了解前序遍歷之后捶惜，也就能很輕易地寫出中序和后序的代碼田藐，這里不再贅述。
二、二叉樹遞歸實戰(zhàn)
1. 二叉樹的深度
Leetcode地址：104. 二叉樹的最大深度
這道題要求的是二叉樹的深度汽久，或者說高度鹤竭，也就是求二叉樹根節(jié)點到最遠(yuǎn)的葉節(jié)點所經(jīng)過的節(jié)點數(shù)。下方的二叉樹深度為3回窘，因為從根節(jié)點3到葉節(jié)點15和到葉節(jié)點7都要經(jīng)過3個節(jié)點诺擅。
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. 翻轉(zhuǎn)二叉樹
Leetcode地址：226. 翻轉(zhuǎn)二叉樹
例：
輸入：
4
/ \
2 7
/ \ / \
1 3 6 9
輸出：
4
/ \
7 2
/ \ / \
9 6 3 1
可以看到舷丹，翻轉(zhuǎn)二叉樹時會將所有節(jié)點的左右子樹都進(jìn)行一次翻轉(zhuǎn)抒钱。相對于根節(jié)點，節(jié)點2和節(jié)點7的位置進(jìn)行了對調(diào)颜凯，而相對于節(jié)點2谋币，節(jié)點3和節(jié)點1的位置進(jìn)行了對調(diào)……因此可以通過遞歸來對每個節(jié)點的左右子樹進(jìn)行對調(diào)，在遇到空樹時退出遞歸症概。
TreeNode* invertTree(TreeNode* root) {
invert(root);
return root;
}
void invert(TreeNode* root) {
if (root == NULL) return;
// 對調(diào)左右子樹
TreeNode* tmp = root->left;
root->left = root->right;
root->right = tmp;
// 遞歸左右子樹
invert(root->left);
invert(root->right);
}
3. 相同的樹
Leetcode地址：100. 相同的樹
該題要判斷兩個二叉樹是否相同蕾额。只有兩個二叉樹的結(jié)構(gòu)相同并且每個節(jié)點上的值相同，它們才是相同的樹彼城。
既然要判斷所有的節(jié)點诅蝶，那么很顯然可以用遞歸求解：假設(shè)當(dāng)前有兩個二叉樹root1和root2，如果其中一個為空而另一個不為空募壕，返回false调炬；如果兩個都為空，返回true舱馅；如果都不為空缰泡，則判斷這兩個節(jié)點的值是否相同，不同則返回false习柠，相同的話則再判斷它們的左右子樹是否相同匀谣。
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == NULL && q == NULL) return true; // 兩個節(jié)點都為空時代表相同
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. 合并二叉樹
給定兩個二叉樹，想象當(dāng)你將它們中的一個覆蓋到另一個上時资溃，兩個二叉樹的一些節(jié)點便會重疊武翎。
你需要將他們合并為一個新的二叉樹。合并的規(guī)則是如果兩個節(jié)點重疊溶锭，那么將他們的值相加作為節(jié)點合并后的新值宝恶，否則不為 NULL 的節(jié)點將直接作為新二叉樹的節(jié)點。
例：
輸入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
輸出:
合并后的樹:
3
/ \
4 5
/ \ \
5 4 7
這道題很明顯也是一道遞歸題，我們需要同時遍歷兩棵樹垫毙，如果當(dāng)前節(jié)點都不為空霹疫，則將兩個值相加形成新的節(jié)點；如果其中一個為空综芥，則以該節(jié)點的值新建節(jié)點丽蝎；如果都為空，則返回空膀藐。
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 != NULL && t2 != NULL) { // 都不為空屠阻，則將兩個節(jié)點的值相加
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. 從前序與中序遍歷序列構(gòu)造二叉樹
Leetcode地址：105. 從前序與中序遍歷序列構(gòu)造二叉樹
例：
前序遍歷preorder = [3, 9, 20, 15, 7]
中序遍歷 inorder = [9, 3, 15, 20, 7]
返回如下的二叉樹：
3
/ \
9 20
/ \
15 7
根據(jù)上面的例子，前序遍歷的第一個節(jié)點3就是二叉樹的根節(jié)點额各，在中序遍歷中找到3国觉，中序遍歷中，3之前的就是左子樹的節(jié)點虾啦，3之后的就是右子樹的節(jié)點麻诀。那么左子樹的前序遍歷就是[9]，中序遍歷也是[9]傲醉，所以左子樹只有一個值為9的節(jié)點蝇闭。右子樹的前序遍歷為[20, 15, 7]，中序遍歷為[15, 20, 7]硬毕，那么右子樹的根節(jié)點就是15丁眼，以此類推……
很容易發(fā)現(xiàn)這也是一個遞歸的程序：前序遍歷的第一個值就是根節(jié)點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;
}
// 新建根節(jié)點
TreeNode* root = new TreeNode(preorder[s1]);
// 找到中間節(jié)點
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 {
// 遞歸調(diào)用
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. 從中序與后序遍歷序列構(gòu)造二叉樹
三、二叉搜索樹
二叉搜索樹(Binary Search Tree)也叫二叉排序樹慎恒，簡稱為BST任内。它具有這樣的性質(zhì)：若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值融柬； 若它的右子樹不空死嗦，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值； 它的左粒氧、右子樹也分別為二叉搜索樹越除。(仔細(xì)觀察可以發(fā)現(xiàn)，二叉搜索樹的中序遍歷可以得到一個有序數(shù)組)。
在二叉搜索樹中查找某個值的操作類似有序數(shù)組中的二分查找摘盆，時間復(fù)雜度都是O(logn)翼雀，但是在BST中插入新的值比在有序數(shù)組中要快得多，因為在BST中插入新的值孩擂，只需使用O(logn)的時間找到插入點然后插入即可狼渊；而在有序數(shù)組中，找到插入點之后需要將該點之后的元素都向后移動一位类垦，移動多個元素的操作非常消耗時間狈邑。
以下圖的二叉搜索樹為例，在其中進(jìn)行查找和插入的操作护锤。
① 查找元素7：從根節(jié)點開始查找官地，根節(jié)點為15，而要查找的值7小于15烙懦，則去節(jié)點15的左子樹進(jìn)行查找驱入；查找到節(jié)點6時，發(fā)現(xiàn)要查找的值7大于6氯析，則去節(jié)點6的右子樹進(jìn)行查找亏较；查找到節(jié)點7，找到結(jié)果掩缓，退出雪情。
② 插入元素19：開始時與查找過程類似，直到找到節(jié)點20你辣，發(fā)現(xiàn)19比20小且20的左子樹為空巡通，則將19插入到節(jié)點20的左子樹。
有時二叉搜索樹的插入順序不理想舍哄，那么會得到一棵偏向一邊的BST宴凉，這時的BST就退化成了鏈表。如下所示表悬，對于這幾個數(shù)據(jù)弥锄，我們期望的BST肯定是左邊這樣的，但是如果我們按1->2->3->4->5->6這樣的順序插入蟆沫，就會得到右邊這樣的BST籽暇。因此如果給定一個有序數(shù)組來構(gòu)建二叉搜索樹，需要挑選中間的值來作為根節(jié)點饭庞。
四戒悠、二叉搜索樹實戰(zhàn)
1. 二叉搜索樹中的搜索
Leetcode地址：700. 二叉搜索樹中的搜索
這道題思路很清楚：假設(shè)從節(jié)點root開始查找value，如果value == root->val但绕，則找到結(jié)果救崔；如果value < root->val惶看，則移動到root->left進(jìn)行查找；否則移動到root->right進(jìn)行查找六孵。如果查找完整棵樹還沒有發(fā)現(xiàn)纬黎，就返回空。
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. 二叉搜索樹中的插入操作
在對二叉樹進(jìn)行插入操作之前需要先找到插入點劫窒，而尋找插入點與上一題的搜索類似本今，當(dāng)找到為空的地方時就可以將當(dāng)前節(jié)點插入。
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) { // 找到為空的分支, 即可插入當(dāng)前節(jié)點
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. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
Leetcode地址：108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
題目要求將一個按照升序排列的有序數(shù)組主巍，轉(zhuǎn)換為一棵高度平衡二叉搜索樹冠息。既然要求BST高度平衡，那么肯定要將數(shù)組中間的值作為根節(jié)點孕索，而左子樹的根節(jié)點則是數(shù)組左半部分的中間值逛艰，右子樹的根節(jié)點是數(shù)組右半部分的中間值……依次遞歸
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.size() == 0) return NULL; // 如果數(shù)組為空, 返回空樹
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]); // 用數(shù)組中間值新建一個節(jié)點
if (start <= middle - 1) { // 如果左邊還有數(shù)據(jù)
generateBST(nums, ptr->left, start, middle - 1);
}
if (middle + 1 <= end) { // 如果右邊還有數(shù)據(jù)
generateBST(nums, ptr->right, middle + 1, end);
}
}
上述代碼用到了C++中的引用，如果不習(xí)慣這種調(diào)用方式搞旭，可以這么寫散怖。
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.size() == 0) return NULL;
return build(nums, 0, nums.size() - 1);
}
// 構(gòu)建完一個節(jié)點之后直接返回
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;
}
