Leetcode刷题100天—701. 二叉搜索树中的插入操作( 二叉树)—day34

柔光的暖阳◎ 2022-09-13 11:23 142阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210910152622593][]

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

难度中等212收藏分享切换为英文接收动态反馈

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

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

**示例 1：**

![img][]

输入：root = [4,2,7,1,3], val = 5
    输出：[4,2,7,1,3,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` 和 `10^4` 之间
 *  每个节点都有一个唯一整数值，取值范围从 `0` 到 `10^8`
 *  `-10^8 <= val <= 10^8`
 *  新值和原始二叉搜索树中的任意节点值都不同

## 错误写法 ##

> 卡了好久，一直没想明白，原来指向这个节点后就不能更改了

以下是错误代码示例

## 正确写法 ##

package 二叉树;
    
    public class _701_二叉搜索树中的插入操作 { 
    // 二叉搜索树的性质,右边比左边大
        public TreeNode insertIntoBST(TreeNode root, int val) { 
            if(root==null){ 
                return new TreeNode(val);
            }
    // 定义一个指针
        	TreeNode node=root;
    // 遍历到指针为空
        	while(node!=null) { 
        		if (val<node.val) { 
    				if (node.left==null) { 
    					node.left=new TreeNode(val);
    					break;
    				}else { 
    					node=node.left;
    				}
    			}else { 
    				if (node.right==null) { 
    					node.right=new TreeNode(val);
    					break;
    				}else { 
    					node=node.right;
    				}
    			}
    // node=val<node.val?node.left:node.right;
        	}
        	
        	
        	return root;
        	
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210910152622593]: /images/20220828/e20ed5c9c35746a898de9faa0f6ce120.png
[701.]: https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
[img]: /images/20220828/2619de33b2d6457db497128f7e767784.png