通過(guò)之前的文章 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的框架思維，二叉樹(shù)的遍歷框架應(yīng)該已經(jīng)印到你的腦子里了，這篇文章就來(lái)實(shí)操一下，看看框架思維是怎么靈活運(yùn)用，秒殺二叉樹(shù)問(wèn)題的。

PS：本文的大部分代碼都做成圖片形式，因?yàn)槲谋敬a左右滑動(dòng)不方便查看，而圖片方便放大、保存，圖片點(diǎn)開(kāi)后也方便左右切換進(jìn)行對(duì)比。

二叉樹(shù)算法的設(shè)計(jì)的總路線(xiàn)：明確一個(gè)節(jié)點(diǎn)要做的事情，然后剩下的事拋給框架。

舉兩個(gè)簡(jiǎn)單的例子體會(huì)一下這個(gè)思路，熱熱身。

1. 如何把二叉樹(shù)所有的節(jié)點(diǎn)中的值加一？

void plusOne(TreeNode root) {
    if (root == null) return;
    root.val += 1;

    plusOne(root.left);
    plusOne(root.right);
}

2. 如何判斷兩棵二叉樹(shù)是否完全相同？

借助框架，上面這兩個(gè)例子不難理解吧？如果可以理解，那么所有二叉樹(shù)算法你都能解決。

下面實(shí)現(xiàn) BST 的基礎(chǔ)操作：判斷 BST 的合法性、增、刪、查。其中「刪」和「判斷合法性」略微復(fù)雜。

二叉搜索樹(shù)（Binary Search Tree，簡(jiǎn)稱(chēng) BST）是一種很常用的的二叉樹(shù)。它的定義是：一個(gè)二叉樹(shù)中，任意節(jié)點(diǎn)的值要大于左子樹(shù)所有節(jié)點(diǎn)的值，且要小于右邊子樹(shù)的所有節(jié)點(diǎn)的值。

如下就是一個(gè)符合定義的 BST：

零、判斷 BST 的合法性

這里是有坑的哦，我們按照剛才的思路，每個(gè)節(jié)點(diǎn)自己要做的事不就是比較自己和左右孩子嗎？看起來(lái)應(yīng)該這樣寫(xiě)代碼：

但是這個(gè)算法出現(xiàn)了錯(cuò)誤，BST 的每個(gè)節(jié)點(diǎn)應(yīng)該要小于右邊子樹(shù)的所有節(jié)點(diǎn)，下面這個(gè)二叉樹(shù)顯然不是 BST，但是我們的算法會(huì)把它判定為 BST。

出現(xiàn)錯(cuò)誤，不要慌張，框架沒(méi)有錯(cuò)，一定是某個(gè)細(xì)節(jié)問(wèn)題沒(méi)注意到。我們重新看一下 BST 的定義，root 需要做的，不僅僅是和左右子節(jié)點(diǎn)比較，而是要和左子樹(shù)和右子樹(shù)的所有節(jié)點(diǎn)比較。怎么辦，鞭長(zhǎng)莫及??！

這種情況，我們可以使用輔助函數(shù)，增加函數(shù)參數(shù)列表，在參數(shù)中攜帶額外信息，請(qǐng)看正確的代碼：

這樣，root 可以對(duì)整棵左子樹(shù)和右子樹(shù)進(jìn)行約束，根據(jù)定義，root 才真正完成了它該做的事，所以這個(gè)算法是正確的。

一、在 BST 中查找一個(gè)數(shù)是否存在

根據(jù)我們的總路線(xiàn)，可以這樣寫(xiě)代碼：

這樣寫(xiě)完全正確，充分證明了你的框架性思維已經(jīng)養(yǎng)成?，F(xiàn)在你可以考慮一點(diǎn)細(xì)節(jié)問(wèn)題了：如何充分利用信息，把 BST 這個(gè)“左小右大”的特性用上？

很簡(jiǎn)單，其實(shí)不需要遞歸地搜索兩邊，類(lèi)似二分查找思想，可以根據(jù) target 和 root.val 的大小比較，就能排除一邊。我們把上面的思路稍稍改動(dòng)：

于是，我們對(duì)原始框架進(jìn)行改造，抽象出一套針對(duì) BST 的遍歷框架：

二、在 BST 中插入一個(gè)數(shù)

對(duì)數(shù)據(jù)結(jié)構(gòu)的操作無(wú)非遍歷 + 訪問(wèn)，遍歷就是「找」，訪問(wèn)就是「改」。具體到這個(gè)問(wèn)題，插入一個(gè)數(shù)，就是先找到插入位置，然后進(jìn)行插入操作。

上一個(gè)問(wèn)題，我們總結(jié)了 BST 中的遍歷框架，就是解決了「找」的問(wèn)題。直接套框架，加上「改」的操作即可。

一旦涉及「改」，函數(shù)就要返回 TreeNode 類(lèi)型，并且對(duì)遞歸調(diào)用的返回值進(jìn)行接收。

三、在 BST 中刪除一個(gè)數(shù)

這個(gè)問(wèn)題稍微復(fù)雜，不過(guò)你有框架指導(dǎo)，難不住你。跟插入操作類(lèi)似，先「找」再「改」，先把框架寫(xiě)出來(lái)再說(shuō)：

找到目標(biāo)節(jié)點(diǎn)了，比方說(shuō)是節(jié)點(diǎn) A，如何刪除這個(gè)節(jié)點(diǎn)，這是難點(diǎn)。因?yàn)閯h除節(jié)點(diǎn)的同時(shí)不能破壞 BST 的性質(zhì)。有三種情況，用圖片來(lái)說(shuō)明。

情況 1：A 恰好是末端節(jié)點(diǎn)，兩個(gè)子節(jié)點(diǎn)都為空，那么它可以當(dāng)場(chǎng)去世。

圖片來(lái)自 www.leetcode.com

if (root.left == null && root.right == null)
    return null;

情況 2：A 只有一個(gè)非空子節(jié)點(diǎn)，那么它要讓這個(gè)孩子接替自己的位置。

圖片來(lái)自 www.leetcode.com

情況 3：A 有兩個(gè)子節(jié)點(diǎn)，麻煩了，為了不破壞 BST 的性質(zhì)，A 必須找到左子樹(shù)中最大的那個(gè)節(jié)點(diǎn)，或者右子樹(shù)中最小的那個(gè)節(jié)點(diǎn)來(lái)接替自己。兩種策略是類(lèi)似的，我們以第二種方式講解。

圖片來(lái)自 www.leetcode.com

if (root.left != null && root.right != null) {
    // 找到右子樹(shù)的最小節(jié)點(diǎn)
    TreeNode minNode = getMin(root.right);
    // 把 root 改成 minNode
    root.val = minNode.val;
    // 轉(zhuǎn)而去刪除 minNode
    root.right = deleteNode(root.right, minNode.val);
}

三種情況分析完畢，簡(jiǎn)化一下，填入框架：

刪除操作就完成了。注意一下，這個(gè)刪除操作并不完美，因?yàn)槲覀冏詈貌灰?root.val = minNode.val 這樣通過(guò)修改節(jié)點(diǎn)內(nèi)部的數(shù)據(jù)來(lái)改變節(jié)點(diǎn)，而是通過(guò)一系列略微復(fù)雜的鏈表操作交換 root 和 minNode 兩個(gè)節(jié)點(diǎn)。

因?yàn)榫唧w應(yīng)用中，val 域可能會(huì)很大，修改起來(lái)很耗時(shí)，而鏈表操作無(wú)非改一改指針，而不會(huì)去碰內(nèi)部數(shù)據(jù)。

但這里忽略這個(gè)細(xì)節(jié)，旨在突出 BST 刪除操作的思路，以及借助框架逐層細(xì)化問(wèn)題的思維方式。

四、最后總結(jié)

通過(guò)這篇文章，你學(xué)會(huì)了如下幾個(gè)技巧：

1. 二叉樹(shù)算法設(shè)計(jì)的總路線(xiàn)：把當(dāng)前節(jié)點(diǎn)要做的事做好，其他的交給遞歸框架，不用當(dāng)前節(jié)點(diǎn)操心。

2. 如果當(dāng)前節(jié)點(diǎn)會(huì)對(duì)下面的子節(jié)點(diǎn)有整體性影響，可以通過(guò)輔助函數(shù)加長(zhǎng)參數(shù)列表，借助函數(shù)參數(shù)傳遞信息。這就是遞歸函數(shù)傳遞信息的常用方式。

3. 在二叉樹(shù)框架之上，擴(kuò)展出一套 BST 遍歷框架：

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目標(biāo)，做點(diǎn)什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

4. 掌握了 BST 的基本操作，包括判斷 BST 的合法性以及 BST 中的增、刪、查操作。