题目
给定二叉搜索树BST的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
输入数据保证,新值和原始二叉搜索树中的任意节点值都不同。
示例1
- 输入:root = [40,20,60,10,30,50,70], val = 25
- 输出:[40,20,60,10,30,50,70,null,null,25]
示例2
- 输入: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
- 新值和原始二叉搜索树中的任意节点值都不同
力扣题目链接
《代码随想录》算法公开课
思路
首先添加结点的位置为叶子结点(不考虑替换中间结点再构建树)。
再来考虑截至条件-当遍历到该结点的子节点都为null时即找到了挂载点。
根据搜索二叉树的特点,即当val
大于root
结点值时,向右树寻找,当val
小于root
结点的值时,向左树寻找。
又因为该题提供的二叉树为搜索二叉树,当找到挂载点是,只需判断该值是否大于pre
(为循环条件中存储的挂载点)。
迭代法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| 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; } }
|
递归法
1 2 3 4 5 6 7 8 9 10 11 12 13
| class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) return new TreeNode(val); if (root.val < val){ root.right = insertIntoBST(root.right, val); }else if (root.val > val){ root.left = insertIntoBST(root.left, val); } return root; } }
|