算法-二叉树篇23-二叉搜索树中的插入操作

二叉搜索树中的插入操作

力扣题目链接

题目描述

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

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

解题思路

我感觉这个方法有点不太合理（必须值和树没有重复的，而且只能插在叶子节点处，虽然插入一个没有什么大问题，但是如果插入元素过多可能会导致树深度较大）解决的方法应该是调整改树，但是目前没有想到合适的方法来解决。 查看了一些题解都没有涉及到这个问题，之后如果学习中遇到了，再回来补充一下。

题解就是比较节点直到寻找到合适的位置插入就行，没什么难度。

题解 class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { TreeNode* creat = new TreeNode(val); if(!root){ return creat; } TreeNode* cur = root; while(cur != NULL){ if(val > cur->val){ if(cur->right){ cur = cur->right; } else{ cur->right = creat; break; } } else if(val < cur->val){ if(cur->left){ cur = cur->left; } else { cur->left = creat; break; } } } return root; } };