LeetCode 701.二叉搜索树种的插入操作
给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证,新值和原始二叉搜索树中的任意节点值都不同。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
。
提示:
- 给定的树上的节点数介于 0 和 10^4 之间
- 每个节点都有一个唯一整数值,取值范围从 0 到 10^8
- -10^8 <= val <= 10^8
- 新值和原始二叉搜索树中的任意节点值都不同
思路:
还是用递归法来写,由于是二叉搜索树,每一个节点进行比大小找到插入点即可。空的点即为可插入点,也就是终止条件。
代码如下:
class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) return new TreeNode(val); TreeNode newRoot = root; TreeNode pre = root; while (root != null) { pre = root; if (root.val > val) { root = root.left; } else if (root.val < val) { root = root.right; } } if (pre.val > val) { pre.left = new TreeNode(val); } else { pre.right = new TreeNode(val); } return newRoot; } }
标签:pre,TreeNode,val,Day37,代码,随想录,二叉,root,节点 From: https://www.cnblogs.com/dwj-ngu/p/16964993.html