给定一棵二叉搜索树的根节点和一个插入值 val。请你把这个 val 插入二叉搜索树中并保持这棵树依然是二叉搜索树。你可以返回任意一个合法结果。
例如:输入二叉树
,插入一个 4 ,可能的结果有
,
等等,返回任意一个即可。
数据范围:二叉搜索树节点数满足
,二叉搜索树上节点值满足 ![](https://www.nowcoder.com/equation?tex=1%20%5Cle%20val%20%5Cle%2010%5E9%20%5C)
import java.util.*; public class Solution { public TreeNode insertToBST (TreeNode root, int val) { if(root == null) return null; TreeNode cur = root;//用于遍历 TreeNode p = cur;//用于记录cur的位置 while(cur != null) { if(cur.val > val) { p = cur; cur = cur.left;//放左边 }else { p = cur; cur = cur.right;//放右边 } } TreeNode node = new TreeNode(val); if(p.val > val) { p.left = node; }else { p.right = node; } return root; } }
import java.util.*; public class Solution { public TreeNode insertToBST (TreeNode root, int val) { if (root == null) { return new TreeNode(val); } TreeNode head = root; while (true) { if (root.val < val) { if (root.right == null) { root.right = new TreeNode(val); break; } root = root.right; } else if (root.val > val) { if (root.left == null) { root.left = new TreeNode(val); break; } root = root.left; } else { break; } } return head; } }