LeetCode Day 二叉树第 7 部分-java教程-PHP中文网

LeetCode Day 二叉树第 7 部分

王林

发布： 2024-07-09 17:17:33

转载

484人浏览过

701.插入二叉搜索树

您将获得二叉搜索树（bst）的根节点和要插入到树中的值。返回插入后bst的根节点。保证原bst中不存在新值。

注意，可能存在多种有效的插入方式，只要插入后树仍然是 BST。您可以退回其中任何一个。

示例1：

Image description
输入：root = [4,2,7,1,3]，val = 5
输出：[4,2,7,1,3,5]
说明：另一棵被接受的树是：

示例2：

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

查看详情

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]
示例3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

限制：

树中的节点数将在 [0, 104] 范围内。
-108 所有值 Node.val 都是唯一的。
-108 保证原始 BST 中不存在 val。
原始页面

 public TreeNode insertIntoBST(TreeNode root, int val) {
        如果（根==空）{
            根=新的TreeNode(val);
            返回根；
        }
        if(root.val<val){
            root.right = insertIntoBST(root.right, val);
        }别的{
            root.left = insertIntoBST(root.left, val);
        }
        返回根；
    }

登录后复制

450. 删除 BST 中的节点

* 错误代码

 public TreeNode deleteNode(TreeNode root, int key) {
        如果（根==空）{
            返回根；
        }

        树节点父=根；
        树节点 cur = root;
        布尔 isLeft = false;

        while(cur!=null){
            if(cur.val > key){
                父=当前；
                cur = cur.left;
                左=真；
            }否则 if(cur.val < 键){
                父=当前；
                cur = cur.right;
                左=假；
            }
            // 主要逻辑 我将移动所有键的右侧节点来替换键前位置逻辑，我们也可以使用左侧节点来完成此操作，但这里不行
            别的{
                //1.叶节点
                if(cur.left == null && cur.right == null){
                     父 = linkToParent(父, null, isLeft,root==cur);
                } 
                否则 if(cur.right == null){
                        父 = linkToParent(父, cur.left, isLeft,root==cur);
                }
                否则 if(cur.left == null){
                        父 = linkToParent(父, cur.right, isLeft,root==cur);
                }
                // 当 key 同时具有左右孩子时删除的长逻辑
                别的{
                    if(cur.right.left == null){
                        cur.right.left = cur.left;
                        父 = linkToParent(父, cur.right, isLeft,root==cur);
                    }
                    别的{
                        TreeNode rightParent = cur.right;
                        TreeNode最左= cur.right;
                        while(最左边.left !=null){
                            右父=最左；
                            最左边 = 最左边.left;
                        }
                        // 主要逻辑
                        父 = linkToParent(父, 最左, isLeft,root==cur);
                            最左边的.left = cur.left;
                            最左.右=当前.右;
                        // 现在我们找到元素右子树中的最小元素 
                        if(最左.右==空){
                            rightParent.left = null;

                        }
                        // 右子树中最小的元素有右孩子
                        别的{
                            rightParent.left = leftest.right;
                        }
                    }
                }

            }
                休息;
            }
            返回根；
        }

    公共TreeNode linkToParent（TreeNode父级，TreeNode替换，boolean isLeft，boolean isRoot）{
        如果（是根）{
            父=替换；
        }别的{
            如果（左）{
                父级.left = 替换;
            }别的{
                父级.right = 替换；
            }
        }

        返回父级；
    }

登录后复制

以上就是LeetCode Day 二叉树第 7 部分的详细内容，更多请关注php中文网其它相关文章！