题目来源：https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/

 

思路：只要根据二叉搜索树的特性，将新插入节点的值不断地与树节点值进行比较，然后找到新节点所属的叶子节点位置，插入即好，返回根节点。

C++题解1：迭代法。需要用一个指针保存父节点。

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

C++题解2：递归法，递归函数有返回值。来源代码随想录

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

C++题解3：递归法，递归函数没有返回值，需要记录上一个节点（父节点）。来源代码随想录

class Solution {
private:TreeNode* parent;void traversal(TreeNode* cur, int val) {if (cur == NULL) {TreeNode* node = new TreeNode(val);if (val > parent->val) parent->right = node;else parent->left = node;return;}parent = cur;if (cur->val > val) traversal(cur->left, val);if (cur->val < val) traversal(cur->right, val);return;}public:TreeNode* insertIntoBST(TreeNode* root, int val) {parent = new TreeNode(0);if (root == NULL) {root = new TreeNode(val);}traversal(root, val);return root;}
};