通過之前的文章 學習數(shù)據(jù)結構的框架思維，二叉樹的遍歷框架應該已經(jīng)印到你的腦子里了，這篇文章就來實操一下，看看框架思維是怎么靈活運用，秒殺二叉樹問題的。

PS：本文的大部分代碼都做成圖片形式，因為文本代碼左右滑動不方便查看，而圖片方便放大、保存，圖片點開后也方便左右切換進行對比。

二叉樹算法的設計的總路線：明確一個節(jié)點要做的事情，然后剩下的事拋給框架。

舉兩個簡單的例子體會一下這個思路，熱熱身。

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

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

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

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

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

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

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

如下就是一個符合定義的 BST：

零、判斷 BST 的合法性

這里是有坑的哦，我們按照剛才的思路，每個節(jié)點自己要做的事不就是比較自己和左右孩子嗎？看起來應該這樣寫代碼：

但是這個算法出現(xiàn)了錯誤，BST 的每個節(jié)點應該要小于右邊子樹的所有節(jié)點，下面這個二叉樹顯然不是 BST，但是我們的算法會把它判定為 BST。

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

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

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

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

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

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

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

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

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

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

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

一旦涉及「改」，函數(shù)就要返回 TreeNode 類型，并且對遞歸調用的返回值進行接收。

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

這個問題稍微復雜，不過你有框架指導，難不住你。跟插入操作類似，先「找」再「改」，先把框架寫出來再說：

找到目標節(jié)點了，比方說是節(jié)點 A，如何刪除這個節(jié)點，這是難點。因為刪除節(jié)點的同時不能破壞 BST 的性質。有三種情況，用圖片來說明。

情況 1：A 恰好是末端節(jié)點，兩個子節(jié)點都為空，那么它可以當場去世。

圖片來自 www.leetcode.com

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

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

圖片來自 www.leetcode.com

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

圖片來自 www.leetcode.com

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

三種情況分析完畢，簡化一下，填入框架：

刪除操作就完成了。注意一下，這個刪除操作并不完美，因為我們最好不要像 root.val = minNode.val 這樣通過修改節(jié)點內(nèi)部的數(shù)據(jù)來改變節(jié)點，而是通過一系列略微復雜的鏈表操作交換 root 和 minNode 兩個節(jié)點。

因為具體應用中，val 域可能會很大，修改起來很耗時，而鏈表操作無非改一改指針，而不會去碰內(nèi)部數(shù)據(jù)。

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

四、最后總結

通過這篇文章，你學會了如下幾個技巧：

1. 二叉樹算法設計的總路線：把當前節(jié)點要做的事做好，其他的交給遞歸框架，不用當前節(jié)點操心。

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

3. 在二叉樹框架之上，擴展出一套 BST 遍歷框架：

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

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