首页 > 其他分享 >力扣 701. 二叉搜索树中的插入操作

力扣 701. 二叉搜索树中的插入操作

时间:2022-12-02 00:55:30浏览次数:71  
标签:right TreeNode cur val nullptr 701 力扣 树中 left

701. 二叉搜索树中的插入操作

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

 

示例 1:

输入:root = [4,2,7,1,3], val = 5
输出:[4,2,7,1,3,5]
解释:另一个满足题目要求可以通过的树是:5作为根节点

示例 2:

输入: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
  • 所有值 Node.val 是 独一无二 的。
  • -108 <= val <= 108
  • 保证 val 在原始BST中不存在。

题解

利用两个节点,cur遍历树,curParent作为cur父节点,cur不停遍历,直到为空跳出循环,此时curParent是满足条件的叶子节点,可以将val放在其子节点。这个方法少了很多if节约了时间(可以压倒97%),但是多用了一个节点存父节点。

查看代码
 /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr)
            return new TreeNode(val);
        TreeNode* cur=root;//遍历节点
        TreeNode* curParent=root;//父节点
        while(cur!=nullptr){
            curParent=cur;//更新父节点
            cur=cur->val>val?cur->left:cur->right;//更新cur
        }
        if(curParent->val>val)//放置val
            curParent->left=new TreeNode(val);
        else
            curParent->right=new TreeNode(val);
        return root;
    }
};

 否则需要在循环中做许多判断,时间复杂度增加,但是空间复杂度降低。

查看代码
 /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr)
            return new TreeNode(val);
        TreeNode* cur=root;
        // TreeNode* curParent=root;
        while(cur!=nullptr){
            if(cur->val>val){
                if(cur->left==nullptr){
                    cur->left=new TreeNode(val);
                    break;
                } 
                else
                    cur=cur->left;
            }
            else if(cur->val<val){
                if(cur->right==nullptr){
                    cur->right=new TreeNode(val);
                    break;
                } 
                else
                    cur=cur->right;
            }      
        }
        return root;
    }
};

标签:right,TreeNode,cur,val,nullptr,701,力扣,树中,left
From: https://www.cnblogs.com/fudanxi/p/16943241.html

相关文章

  • 力扣 700. 二叉搜索树中的搜索
    700.二叉搜索树中的搜索给定二叉搜索树(BST)的根节点 root 和一个整数值 val。你需要在BST中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节......
  • 力扣 669. 修剪二叉搜索树
    669.修剪二叉搜索树给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low,high]中。修剪树 不应该......
  • 二叉树中序遍历非递归算法实现 cpp
    二叉树中序遍历非递归算法实现#include<iostream>//二叉树中序遍历非递归算法实现usingnamespacestd;#defineMAXSIZE100/*不让用递归,那就用栈!!*///树的结点......
  • 力扣刷题笔记 167. 两数之和 II - 输入有序数组
    问题描述给你一个下标从1开始的整数数组numbers,该数组已按非递减顺序排列,请你从数组中找出满足相加之和等于目标数 target的两个数。如果设这两个数分别是numbers[ind......
  • 力扣 leetcode 844. 比较含退格的字符串
    问题描述给定s和t两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回true。#代表退格字符。注意:如果对空文本输入退格字符,文本继续为空。提示:1......
  • 力扣 leetcode 15. 三数之和
    问题描述给你一个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k,同时还满足nums[i]+nums[j]+nums[k]==0。请你......
  • 剑指offer:二叉树中和为某一值的路径
    题目描述输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。/***Definiti......
  • 二叉树中序遍历(python)
    def inorder(self, list: List[int], root: TreeNode):        # 遇到空节点则返回        if not root:            return ......
  • 「模拟」找到最近的有相同 X 或 Y 坐标的点(力扣第1779题)
    本题为12月1日力扣每日一题题目来源:力扣第1779题题目tag:模拟题面题目描述给你两个整数 x和 y ,表示你在一个笛卡尔坐标系下的 (x,y) 处。同时,在同一个坐标......
  • 力扣275(jav&python)-H 指数 II(中等)
    题目:给你一个整数数组citations,其中citations[i]表示研究者的第i篇论文被引用的次数,citations已经按照 升序排列 。计算并返回该研究者的h 指数。h指数的定......