插入二叉搜索树Leetcode解决方案


难度级别 中等
经常问 亚马逊 Apple Atlassian的 Facebook 谷歌 微软
二进制搜索树

在这个问题中,我们得到一个根节点 二进制搜索树 包含整数值和必须在Binary Search Tree中添加的节点的整数值并返回其结构。 将元素插入BST之后,我们必须打印其有序遍历。

使用案列

Binary Search Tree:
 
    7
 
  /     \

3         10

        /

      8
Integer Value = 11
3 7 8 10 11
Binary Search Tree:
           5

         /

       4

     /

   3
Integer Value = 2
2 3 4 5

说明

插入二叉搜索树Leetcode解决方案

插入二叉搜索树Leetcode解决方案

方法(递归)

为了确定应在二进制搜索树中插入任何给定节点的位置,我们必须设置从根到其左/右子节点将是给定节点的相应节点的路径。

我们可以通过将任务从问题传递到子问题来递归解决。 在这种情况下,将新节点插入树意味着将其插入到其左子树或右子树中。 同样的想法也适用于任何其他子树。 我们需要建立一个基本案例。 当我们到达任何子树的根节点为 ,这意味着我们已经到达插入目标节点的路径的末尾。 因此,我们返回一个 新 具有节点值作为给定值的节点地址。 二进制搜索树具有显着的优势,可以搜索其中的任意元素 O(logN) 平均情况下的时间。 因此,在这种情况下,我们找到了要在有效时间内插入的新节点的位置。

算法

  1. 创建一个功能 insertIntoBST() 它返回的地址 插入给定后的BST 节点
  2. insertIntoBST() 有两个参数: 树的和 要插入的节点数
  3. 该函数将执行以下操作:
    • If is NULL, 返回值与给定值相同的新树节点
    • 如果给定的值是 更大的 比...的价值 节点,然后将相同的问题调用到正确的子树,然后返回根
      • 根权 = insertIntoBST(根->权利,价值)
      • 回报
    • 在左侧子树中的其他搜索为:
      • 左根= insertIntoBST(root.left,值)
      • 回报
  4. 打印二进制搜索树的有序遍历

插入二叉搜索树Leetcode解决方案的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
    return;
}


BSTNode* insertIntoBST(BSTNode* root , int val)
{
    if(root == NULL)
        return new BSTNode(val);
    if(val > root->value)
    {
        root->right = insertIntoBST(root->right , val);
        return root;
    }
    root->left = insertIntoBST(root->left , val);
    return root;
}

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

Java程序

class BSTNode
{
    int value;
    BSTNode left , right;

    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        if(val > root.value)
        {
            root.right = insertIntoBST(root.right , val);
            return root;
        }
        root.left = insertIntoBST(root.left , val);
        return root;
    }

    static void inorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.value + " ");
        inorderTraversal(root.right);
        return;
    }
}

3 7 8 10 11

插入二叉搜索树Leetcode解决方案的复杂性分析

时间复杂度

哦) = BST的高度= 登录 (其中N = BST中的节点数)在一般情况下(当我们进行logN递归调用时)。 但 上) 在最坏的情况下,树是倾斜的。 因为如果树倾斜,搜索将变成 线性 一。

空间复杂度

哦) 在一般情况下。 上) 在最坏的情况下。 这里的空间复杂度与时间复杂度相同,因为它取决于我们进行的递归调用的数量。

方法(迭代)

我们可以迭代地遵循上述方法来改善空间复杂性。 递归使用消耗内存的堆栈帧。 因此,在迭代解决方案中,我们防止了 递归调用负载 然后沿着我们的搜索路径上的树往下走,直到我们碰到一个节点,该节点的左边或右边是 。 当我们有 root.left / root.right = NULL, 我们将此节点设置为等于值与给定值相同的新节点。 请注意,我们通过将值与 根 每个递归调用中的值。

算法

  1. 我们又有一个 insertIntoBST() 出于与上述相同的目的
  2. 如果 根 一片空白
    1. 返回值与给定值相同的新节点
  3. 创建根的副本,例如 假的 操纵BST的内容
  4. 假的 is 不是
    1. 如果给定值大于 根值
      1. If 根权 一片空白
        1. 根权 =具有给定值的新节点
        2. 回报
      2. 其他,设置
        1. = 根权,跳到右边的子树
    2. 否则,如果该值小于或等于 根值
      1. 如果root.left为NULL
        1. 左根 =具有给定值的新节点
        2. 回报
      2. 其他,设置
        1. = 左根,跳到左侧子树
  5. 打印BST的顺序遍历

插入二叉搜索树Leetcode解决方案的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
    return;
}

BSTNode* insertIntoBST(BSTNode* root , int val)
{
    if(root == NULL)
        return new BSTNode(val);
    BSTNode* dummy = root;
    while(dummy != NULL)
    {
        if(val > dummy->value)
        {
            if(dummy->right == NULL)
            {
                dummy->right = new BSTNode(val);
                return root;
            }
            else
                dummy = dummy->right;
        }
        else
        {
            if(dummy->left == NULL)
            {
                dummy->left = new BSTNode(val);
                return root;
            }
            else
                dummy = dummy->left;
        }
    }
    return root;
}

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

Java程序

class BSTNode
{
    int value;
    BSTNode left , right;

    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        BSTNode dummy = root;
        while(dummy != null)
        {
            if(val > dummy.value)
            {
                if(dummy.right == null)
                {
                    dummy.right = new BSTNode(val);
                    return root;
                }
                else
                    dummy = dummy.right;
            }
            else
            {
                if(dummy.left == null)
                {
                    dummy.left = new BSTNode(val);
                    return root;
                }
                else
                    dummy = dummy.left;
            }
        }
        return root;
    }

    static void inorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.value + " ");
        inorderTraversal(root.right);
        return;
    }
}

3 7 8 10 11

插入二叉搜索树Leetcode解决方案的复杂性分析

时间复杂度

哦) = BST的高度= 登录 (其中N = BST中的节点数)在一般情况下。 但 上) 在最坏的情况下,树是倾斜的。 同样,时间复杂度取决于我们到达目标之前要进行的迭代次数,在该迭代之后应插入给定节点,并且取决于树的结构。

空间复杂度

O(1)。 即使在最坏的情况下,我们也只对变量使用恒定的空间。