给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。
Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。
Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
例如,
给定二叉搜索树: 4 / \ 2 7 / \ 1 3 和 插入的值: 5
你可以返回这个二叉搜索树:
4 / \ 2 7 / \ / 1 3 5
或者这个树也是有效的:
5 / \ 2 7 / \ 1 3 \ 4
二叉搜索树的插入操作与搜索操作类似,对于每个节点:
Java:
class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) return new TreeNode(val); if (val > root.val) root.right = insertIntoBST(root.right, val); else root.right = insertIntoBST(root.right, val); return root; } }
Python:
class Solution: def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode: if not root: return TreeNode(val) if val > root.val: root.right = self.insertIntoBST(root.right, val) else: root.left = self.insertIntoBST(root.left, val) return root
Golang:
func insertIntoBST(root *TreeNode, val int) *TreeNode { if root == nil { t := new(TreeNode) t.Val = val return t } if val > root.Val { root.Right = insertIntoBST(root.Right, val) } else { root.Left = insertIntoBST(root.Left, val) } return root }
Java:
class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { TreeNode node = root; while (node != null) { if (val > node.val) { if (node.right == null) { node.right = new TreeNode(val); return root; } else node = node.right; } else { if (node.left == null) { node.left = new TreeNode(val); return root; } else node = node.left; } } return new TreeNode(val); } }
Python:
class Solution: def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode: node = root while node: if val > node.val: if not node.right: node.right = TreeNode(val) return root else: node = node.right else: if not node.left: node.left = TreeNode(val) return root else: node = node.left return TreeNode(val)
Golang:
func insertIntoBST(root *TreeNode, val int) *TreeNode { t := new(TreeNode) t.Val = val node := root for node != nil { if val > node.Val { if node.Right == nil { node.Right = t return root } else { node = node.Right } } else { if node.Left == nil { node.Left = t return root } else { node = node.Left } } } return t }
本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug
原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。
原始发表时间:2020-03-16
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句