本文共 3048 字，大约阅读时间需要 10 分钟。

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.

For example, 

Given the tree:        4       / \      2   7     / \    1   3And the value to insert: 5

You can return this binary search tree:

4       /   \      2     7     / \   /    1   3 5

This tree is also valid:

5	       /   \      2     7     / \       1   3         \          4

Constraints:

• The number of nodes in the given tree will be between 0 and 10^4.
• Each node will have a unique integer value from 0 to -10^8, inclusive.
• -10^8 <= val <= 10^8
• It's guaranteed that val does not exist in the original BST.

题意：给定二叉搜索树的根节点和要插入树中的值，将值插入二叉搜索树，返回插入后二叉搜索树的根节点。 这里保证原始二叉搜索树中不存在新值。

题目提示我们，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。

思路1：递归插入

class Solution {
   public:    TreeNode* insertIntoBST(TreeNode* root, int val) {
           if (root == nullptr) return new TreeNode(val);        if (val < root->val) root->left = insertIntoBST(root->left, val);        else root->right = insertIntoBST(root->right, val);        return root;    }};

效率如下，感觉好低啊：

执行用时：176 ms, 在所有 C++ 提交中击败了5.65% 的用户内存消耗：56 MB, 在所有 C++ 提交中击败了5.08% 的用户

思路2：迭代插入

先找到要插入的地方及其父结点，然后比较值，插入为左结点或右结点：

class Solution {
   public:    TreeNode* insertIntoBST(TreeNode* root, int val) {
           if (root == nullptr) return new TreeNode(val);        TreeNode *temp = root, *father = root;        while (temp) {
               father = temp;            temp = val < temp->val ? temp->left : temp->right;        }        if (val < father->val) father->left = new TreeNode(val);        else father->right = new TreeNode(val);        return root;    }};

效率也很低：

执行用时：168 ms, 在所有 C++ 提交中击败了5.65% 的用户内存消耗：55.8 MB, 在所有 C++ 提交中击败了5.08% 的用户

用Java提交一下：

class Solution {
       public TreeNode insertIntoBST(TreeNode root, int val) {
           if (root == null) return new TreeNode(val);        TreeNode temp = root, father = root;        while (temp != null) {
               father = temp;            temp = val < temp.val ? temp.left : temp.right;        }        if (val < father.val) father.left = new TreeNode(val);        else father.right = new TreeNode(val);        return root;    }}

这是赤裸裸的作弊吧？？？

执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户内存消耗：39.4 MB, 在所有 Java 提交中击败了56.71% 的用户

2020/9/30 Update：Python代码如下：

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, val=0, left=None, right=None):#         self.val = val#         self.left = left#         self.right = rightclass Solution:    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:        if not root:             return TreeNode(val)        if val < root.val:            root.left = self.insertIntoBST(root.left, val)        else:            root.right = self.insertIntoBST(root.right, val)        return root

转载地址：https://memcpy0.blog.csdn.net/article/details/108813661 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！