力扣701 二叉搜索树中的插入操作 java实现

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

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

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

示例 1：

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

由于该题不要求是平衡二叉树，所以只需要按照构造来即可。即递归二叉搜索树，若给出的值比当前节点的值大，则向右递归，若比当前节点小则向左递归，直至最终遇到空节点。具体代码如下：

public static void main(String[] args) { // 测试用 TreeNode treeNode1 = new TreeNode(4); treeNode1.left = new TreeNode(2); treeNode1.right = new TreeNode(7); treeNode1.left.left = new TreeNode(1); treeNode1.left.right = new TreeNode(3); System.out.println(insertIntoBST(treeNode1, 5)); } public static TreeNode insertIntoBST(TreeNode root, int val) { if (root == null){ root = new TreeNode(val); return root; } if (val > root.val){ // 大于当前值则向右递归，反之向左递归 root.right = insertIntoBST(root.right, val); }else { root.left = insertIntoBST(root.left, val); } return root; }

以上为记录分享用，代码较差请见谅