判定表与判定树的画法_⼆叉搜索树操作集锦
读完本⽂，你可以去⼒扣拿下如下题⽬：
100.相同的树
450.删除⼆叉搜索树中的节点
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; // ⼀个为空，⼀个⾮空，显然借助框架，上⾯这两个例⼦不难理解吧？如果可以理解，那么所有⼆叉树算法你都能解决。
⼆叉搜索树(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
但是这个算法出现了错误，BST 的每个节点应该要⼩于右边⼦树的所有节点，下⾯这个⼆叉树显然不是 BST，但是我们的算法会把它判定
为 BST。
出现错误，不要慌张，框架没有错，⼀定是某个细节问题没注意到。我们重新看⼀下 BST 的定义，root 需要做的不只是和左右⼦节点⽐
较，⽽是要整个左⼦树和右⼦树所有节点⽐较。怎么办，鞭长莫及啊！
这种情况，我们可以使⽤辅助函数，增加函数参数列表，在参数中携带额外信息，请看正确的代码：
boolean isValidBST(TreeNode root) { return isValidBST(root, null, null);}b oolean isValidBST(TreeNode root, TreeNode min, TreeNode max) { if (root == null) r
⼀、在 BST 中查⼀个数是否存在
根据我们的指导思想，可以这样写代码：
boolean isInBST(TreeNode root, int target) { if (root == null) return false; if (root.val == target) return true; return isInBST(root.left, target) || isInBST(roo
这样写完全正确，充分证明了你的框架性思维已经养成。现在你可以考虑⼀点细节问题了：如何充分利⽤信息，把 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 isInBS
于是，我们对原始框架进⾏改造，抽象出⼀套针对 BST 的遍历框架：
void BST(TreeNode root, int target) { if (root.val == target) // 到⽬标，做点什么 if (root.val < target) BST(root.right, target); if (root.val > target) ⼆、在 BST 中插⼊⼀个数
对数据结构的操作⽆⾮遍历 + 访问，遍历就是“”，访问就是“改”。具体到这个问题，插⼊⼀个数，就是先到插⼊位置，然后进⾏
插⼊操作。
上⼀个问题，我们总结了 BST 中的遍历框架，就是“”的问题。直接套框架，加上“改”的操作即可。⼀旦涉及“改”，函数就要返回TreeNode 类型，并且对递归调⽤的返回值进⾏接收。
TreeNode insertIntoBST(TreeNode root, int val) { // 到空位置插⼊新节点 if (root == null) return new TreeNode(val); // if (root.val == val) // BST 中⼀般不三、在 BST 中删除⼀个数
这个问题稍微复杂，不过你有框架指导，难不住你。跟插⼊操作类似，先“”再“改”，先把框架写出来再说：
中国最高建筑TreeNode deleteNode(TreeNode root, int key) { if (root.val == key) { // 到啦，进⾏删除 } else if (root.val > key) { root.left = deleteNode(root.left, key
到⽬标节点了，⽐⽅说是节点 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;
三种情况分析完毕，填⼊框架，简化⼀下代码：
TreeNode deleteNode(TreeNode root, int key) { if (root == null) return null; if (root.val == key) { // 这两个 if 把情况 1 和 2 都正确处理了 if (root.left == n
删除操作就完成了。注意⼀下，这个删除操作并不完美，因为我们⼀般不会通过 root.val = minNode.val 修改节点内部的值来交换节点，
⽽是通过⼀系列略微复杂的链表操作交换 root 和 minNode 两个节点。因为具体应⽤中，val 域可能会很⼤，修改起来很耗时，⽽链表操
作⽆⾮改⼀改指针，⽽不会去碰内部数据。
但这⾥忽略这个细节，旨在突出 BST 基本操作的共性，以及借助框架逐层细化问题的思维⽅式。
四、最后总结
通过这篇⽂章，你学会了如下⼏个技巧：
火影忍者晓组织成员1. ⼆叉树算法设计的总路线：把当前节点要做的事做好，其他的交给递归框架，不⽤当前节点操⼼。
2. 如果当前节点会对下⾯的⼦节点有整体影响，可以通过辅助函数增长参数列表，借助参数传递信息。
3. 在⼆叉树框架之上，扩展出⼀套 BST 遍历框架：
void BST(TreeNode root, int target) { if (root.val == target) // 到⽬标，做点什么 if (root.val < target) BST(root.right, target); if (root.val > target) 4. 掌握了 BST 的基本操作。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论