LeetCode - 按标签分类刷题（二叉搜索树题解）

本文主要是介绍LeetCode - 按标签分类刷题（二叉搜索树题解），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

LeetBook- 二叉搜索树

对LeetBool 二叉搜索树的自我总结

以上是LeetCode的二叉搜索树的分类题目，总结起来就是利用二叉搜索树的中序遍历是升序的进行各种变式，其中：

• 二叉搜索树的查找，插入，删除操作（重点关注）
  • 搜索操作 是进行循环判断，如果大于根节点，则看右节点；如果小于根节点则看左节点
  • 插入操作，以要插入的节点的值大小来决定插入到哪个子树中
    • 如果该子树不为空，则问题转化成了将 val 插入到对应子树上。（递归）
    • 否则，在此处新建一个以 val 为值的节点，并链接到其父节点 root 上。
  • 删除操作（☆☆☆☆☆）
  1. 如果目标节点没有子节点，我们可以直接移除该目标节点。
  2. 如果目标节只有一个子节点，我们可以用其子节点作为替换。
  3. 如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点。

例 1：目标节点没有子节点
例 2：目标节只有一个子节点

例 3：目标节点有两个子节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int successor(TreeNode root){
        root = root.right;
        while(root.left != null){
            root = root.left;
        }
        return root.val;
    }
    public int predecessor(TreeNode root){
        root = root.left;
        while(root.right != null){
            root = root.right;
        }
        return root.val;
    }
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null){
            return null;
        }
        if(key > root.val){
            root.right = deleteNode(root.right,key);
        }else if(key < root.val){
            root.left = deleteNode(root.left,key);
        }else{
            if(root.left == null && root.right == null){
                root = null;
            }
            else if(root.right != null){
                root.val = successor(root);
                root.right = deleteNode(root.right,root.val);
            }
            else{
                root.val = predecessor(root);
                root.left = deleteNode(root.left,root.val);
            }
        }
        return root;
    }
}

这篇关于LeetCode - 按标签分类刷题（二叉搜索树题解）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！