讀完本文，你可以去力扣拿下如下題目：
100.相同的樹
701.二叉搜尋樹中的插入操作
700.二叉搜尋樹中的搜尋
98.驗證二叉搜尋樹
-----------
透過之前的文章框架思維，二叉樹的遍歷框架應該已經印到你的腦子裡了，這篇文章就來實操一下，看看框架思維是怎麼靈活運用，秒殺一切二叉樹問題的。
二叉樹演算法的設計的總路線：明確一個節點要做的事情，然後剩下的事拋給框架。
void traverse(TreeNode root) { // root 需要做什麼？在這做。 // 其他的不用 root 操心，拋給框架 traverse(root.left); traverse(root.right);}舉兩個簡單的例子體會一下這個思路，熱熱身。
1. 如何把二叉樹所有的節點中的值加一？
void plusOne(TreeNode root) { if (root == null) return; root.val += 1; plusOne(root.left); plusOne(root.right);}2. 如何判斷兩棵二叉樹是否完全相同？
boolean isSameTree(TreeNode root1, TreeNode root2) { // 都為空的話，顯然相同 if (root1 == null && root2 == null) return true; // 一個為空，一個非空，顯然不同 if (root1 == null || root2 == null) return false; // 兩個都非空，但 val 不一樣也不行 if (root1.val != root2.val) return false; // root1 和 root2 該比的都比完了 return isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right);}藉助框架，上面這兩個例子不難理解吧？如果可以理解，那麼所有二叉樹演算法你都能解決。
二叉搜尋樹（Binary Search Tree，簡稱 BST）是一種很常用的的二叉樹。它的定義是：一個二叉樹中，任意節點的值要大於等於左子樹所有節點的值，且要小於等於右邊子樹的所有節點的值。
如下就是一個符合定義的 BST：
下面實現 BST 的基礎操作：判斷 BST 的合法性、增、刪、查。其中“刪”和“判斷合法性”略微複雜。
零、判斷 BST 的合法性
這裡是有坑的哦，我們按照剛才的思路，每個節點自己要做的事不就是比較自己和左右孩子嗎？看起來應該這樣寫程式碼：
boolean isValidBST(TreeNode root) { if (root == null) return true; if (root.left != null && root.val <= root.left.val) return false; if (root.right != null && root.val >= root.right.val) return false; return isValidBST(root.left) && isValidBST(root.right);}但是這個演算法出現了錯誤，BST 的每個節點應該要小於右邊子樹的所有節點，下面這個二叉樹顯然不是 BST，但是我們的演算法會把它判定為 BST。
出現錯誤，不要慌張，框架沒有錯，一定是某個細節問題沒注意到。我們重新看一下 BST 的定義，root 需要做的不只是和左右子節點比較，而是要整個左子樹和右子樹所有節點比較。怎麼辦，鞭長莫及啊！
這種情況，我們可以使用輔助函式，增加函式引數列表，在引數中攜帶額外資訊，請看正確的程式碼：
boolean isValidBST(TreeNode root) { return isValidBST(root, null, null);}boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) { if (root == null) return true; if (min != null && root.val <= min.val) return false; if (max != null && root.val >= max.val) return false; return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);}一、在 BST 中查詢一個數是否存在
根據我們的指導思想，可以這樣寫程式碼：
boolean isInBST(TreeNode root, int target) { if (root == null) return false; if (root.val == target) return true; return isInBST(root.left, target) || isInBST(root.right, target);}這樣寫完全正確，充分證明了你的框架性思維已經養成。現在你可以考慮一點細節問題了：如何充分利用資訊，把 BST 這個“左小右大”的特性用上？
很簡單，其實不需要遞迴地搜尋兩邊，類似二分查詢思想，根據 target 和 root.val 的大小比較，就能排除一邊。我們把上面的思路稍稍改動：
boolean isInBST(TreeNode root, int target) { if (root == null) return false; if (root.val == target) return true; if (root.val < target) return isInBST(root.right, target); if (root.val > target) return isInBST(root.left, target); // root 該做的事做完了，順帶把框架也完成了，妙}於是，我們對原始框架進行改造，抽象出一套針對 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);}二、在 BST 中插入一個數
對資料結構的操作無非遍歷 + 訪問，遍歷就是“找”，訪問就是“改”。具體到這個問題，插入一個數，就是先找到插入位置，然後進行插入操作。
上一個問題，我們總結了 BST 中的遍歷框架，就是“找”的問題。直接套框架，加上“改”的操作即可。一旦涉及“改”，函式就要返回 TreeNode 型別，並且對遞迴呼叫的返回值進行接收。
TreeNode insertIntoBST(TreeNode root, int val) { // 找到空位置插入新節點 if (root == null) return new TreeNode(val); // if (root.val == val) // BST 中一般不會插入已存在元素 if (root.val < val) root.right = insertIntoBST(root.right, val); if (root.val > val) root.left = insertIntoBST(root.left, val); return root;}三、在 BST 中刪除一個數
這個問題稍微複雜，不過你有框架指導，難不住你。跟插入操作類似，先“找”再“改”，先把框架寫出來再說：
TreeNode deleteNode(TreeNode root, int key) { if (root.val == key) { // 找到啦，進行刪除 } else if (root.val > key) { root.left = deleteNode(root.left, key); } else if (root.val < key) { root.right = deleteNode(root.right, key); } return root;}找到目標節點了，比方說是節點 A，如何刪除這個節點，這是難點。因為刪除節點的同時不能破壞 BST 的性質。有三種情況，用圖片來說明。
情況 1：A 恰好是末端節點，兩個子節點都為空，那麼它可以當場去世了。
圖片來自 LeetCode
if (root.left == null && root.right == null) return null;情況 2：A 只有一個非空子節點，那麼它要讓這個孩子接替自己的位置。
圖片來自 LeetCode
// 排除了情況 1 之後if (root.left == null) return root.right;if (root.right == null) return root.left;情況 3：A 有兩個子節點，麻煩了，為了不破壞 BST 的性質，A 必須找到左子樹中最大的那個節點，或者右子樹中最小的那個節點來接替自己。我們以第二種方式講解。
圖片來自 LeetCode
if (root.left != null && root.right != null) { // 找到右子樹的最小節點 TreeNode minNode = getMin(root.right); // 把 root 改成 minNode root.val = minNode.val; // 轉而去刪除 minNode root.right = deleteNode(root.right, minNode.val);}三種情況分析完畢，填入框架，簡化一下程式碼：
TreeNode deleteNode(TreeNode root, int key) { if (root == null) return null; if (root.val == key) { // 這兩個 if 把情況 1 和 2 都正確處理了 if (root.left == null) return root.right; if (root.right == null) return root.left; // 處理情況 3 TreeNode minNode = getMin(root.right); root.val = minNode.val; root.right = deleteNode(root.right, minNode.val); } else if (root.val > key) { root.left = deleteNode(root.left, key); } else if (root.val < key) { root.right = deleteNode(root.right, key); } return root;}TreeNode getMin(TreeNode node) { // BST 最左邊的就是最小的 while (node.left != null) node = node.left; return node;} 刪除操作就完成了。注意一下，這個刪除操作並不完美，因為我們一般不會透過 root.val = minNode.val 修改節點內部的值來交換節點，而是透過一系列略微複雜的連結串列操作交換 root 和 minNode 兩個節點。因為具體應用中，val 域可能會很大，修改起來很耗時，而連結串列操作無非改一改指標，而不會去碰內部資料。
但這裡忽略這個細節，旨在突出 BST 基本操作的共性，以及藉助框架逐層細化問題的思維方式。
四、最後總結
透過這篇文章，你學會了如下幾個技巧：
二叉樹演算法設計的總路線：把當前節點要做的事做好，其他的交給遞迴框架，不用當前節點操心。如果當前節點會對下面的子節點有整體影響，可以透過輔助函式增長引數列表，藉助引數傳遞資訊。在二叉樹框架之上，擴展出一套 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);}