通過(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ì)的總路線：明確一個(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ě)代碼：

這樣寫(xiě)完全正確,，充分證明了你的框架性思維已經(jīng)養(yǎng)成。現(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ì)的總路線：把當(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 中的增、刪,、查操作,。