701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

 

例如, 

给定二叉搜索树:

        4        / \       2   7      / \     1   3

和 插入的值: 5 你可以返回这个二叉搜索树:

         4        /   \       2     7      / \   /     1   3 5 或者这个树也是有效的:

         5        /   \       2     7      / \        1   3          \           4

解题思路

参考代码随想录

力扣传送门

BST插入一个值，就是找到节点为空的时候，将父节点值跟插入值val大小比较再决定插入到父节点的左孩子，还是右孩子。递归的第二种跟迭代的方式其实是之前写BST用到的pre,cur的用法。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { //想象一下三种情况，root为空，val小于root节点值，val 大于root节点值。（题目说节点值的值唯一，也就是说val不会等于root节点值） if(root == nullptr){ //情况1 TreeNode *node = new TreeNode(val); return node; } if(val < root->val){ //情况2 root->left = insertIntoBST(root->left, val); } if(val > root->val){ //情况3 root->right = insertIntoBST(root->right, val); } return root; } }; /**pre\cur方式递归 * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode *pre; void traverse(TreeNode *cur, int val){ if(cur == nullptr){ //如果遇上空间点了，需要根据父节点值与val的大小关系，来决定父节点左孩子还是右孩子指向新节点node TreeNode *node = new TreeNode(val); if(val < pre->val) pre->left = node; else if(val > pre->val) pre->right = node; return; } pre = cur; //没遇上空节点，保存当前节点，作为下次的父节点 if(val < cur->val) traverse(cur->left, val); if(val > cur->val) traverse(cur->right, val); return; } TreeNode* insertIntoBST(TreeNode* root, int val) { pre = new TreeNode(0); if(root == nullptr){ TreeNode *node = new TreeNode(val); return node; } traverse(root, val); return root; } }; /**迭代法 * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if(root == nullptr){ TreeNode *node = new TreeNode(val); return node; } TreeNode *cur = root, *pre; while(cur != nullptr){ pre = cur; if(val < cur->val){ cur = cur->left; } else if(val > cur->val){ cur = cur->right; } } TreeNode *node = new TreeNode(val); if(val < pre->val) pre->left = node; else if(val > pre->val) pre->right = node; return root; } };