二叉搜索树中的插入操作题目链接：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/Given的二叉搜索树(BST)的根节点和要插入到树中的值，将值插入到二叉搜索树中。返回插入后二叉搜索树的根节点。输入数据保证新值不同于原始二叉搜索树中的任何节点值。请注意，可能有不止一种有效的插入方式，只要树在插入后仍然是二叉搜索树即可。您可以返回任何有效结果。提示：给定树上的节点数在0到10^4之间，每个节点都有一个唯一的整数值，范围从0到10^8-10^8<=val<=10^8新值不同于原始二叉搜索树中任何节点的值。其实这道题其实是一道简单的题，只是题中提示：有效的插入方式有很多，二叉查找树也可以重构。这个想法吓跑了很多人，顿时觉得话题复杂了很多。其实可以忽略题中提到的改变树结构的插入方式。从下面的演示视频可以看出：只要按照二叉搜索树的规则进行遍历，遇到空节点就插入节点。二叉搜索树中的插入操作，比如插入元素10，需要找到结束节点并插入。同理插入15号元素，插入0号元素，插入6号元素，需要调整二叉树的结构吗？不必要。.只要遍历二叉搜索树，找到空节点，插入元素，那么这道题其实很简单。下一步是遍历二叉搜索树。Recursive递归三部曲：保证递归函数参数和返回值参数是根节点指针和要插入的元素。递归函数这里有返回值吗？可以，也可以，但是如果递归函数没有返回值，实现起来比较麻烦，下面会给出具体的实现代码。如果有返回值，则可以通过返回值完成新增节点与其父节点之间的赋值操作。（下面进一步解释）递归函数的返回类型是节点类型TreeNode*。代码如下：TreeNode*insertIntoBST(TreeNode*root,intval)判断终止条件终止条件是在发现遍历的节点为null时，找到要插入的节点的位置，返回插入的节点。代码如下：if(root==NULL){TreeNode*node=newTreeNode(val);returnnode;}这里将添加的节点返回给上层，完成父子节点赋值操作，并详情见下文。这个时候判断单级递归的逻辑一定很清楚了。需要遍历整棵树吗？不要忘记这是一棵搜索树。遍历整个搜索树是对搜索树的侮辱，哈哈。搜索树是有方向的，可以根据插入元素的值来确定递归方向。代码如下：if(root->val>val)root->left=insertIntoBST(root->left,val);if(root->valright=insertIntoBST(root->right,val);返回根;至此，大家应该能感受到如何通过递归函数的返回值来完成对新增节点的父子关系赋值操作了。下一层将返回添加的节点。这一层用root->left或root->right接住它。整体代码如下：)root->left=insertIntoBST(root->left,val);if(root->valright=insertIntoBST(root->right,val);returnroot;}};可见代码并不复杂。刚才说了递归函数不需要返回值。也可以找到插入节点位置，直接让其父节点指向插入节点，结束递归。那么递归函数定义如下：TreeNode*parent;//记录遍历节点的父节点voidtraversal(TreeNode*cur,intval)没有返回值，需要记录上一个节点（parent），当你遇到空节点，让父左孩子或右孩子指向新插入的节点。然后结束递归。代码如下：classSolution{private:TreeNode*parent;voidtraversal(TreeNode*cur,intval){if(cur==NULL){TreeNode*node=newTreeNode(val);if(val>parent->val)parent->right=node;elseparent->left=node;return;}parent=cur;if(cur->val>val)遍历(cur->left,val);if(cur->valright,val);return;}public:TreeNode*insertIntoBST(TreeNode*root,intval){parent=newTreeNode(0);if(root==NULL){root=newTreeNode(val);}遍历(root,val);returnroot;}};可见还是比较麻烦的。之所以给出这个例子，是为了说明通过递归函数的返回值可以方便的完成父子节点的赋值。网上相同的代码可能会误导大家认为通过递归函数返回节点是理所当然的。其实这里还有优化！我们再来看看迭代法。如果你不熟悉二叉搜索树的迭代方法，可以看这篇文章：二叉树：二叉搜索树登场！在迭代遍历的过程中，需要记录当前遍历节点的父节点，这样才能进行插入节点的操作。530.二叉搜索树的最小绝对差和501.二叉搜索树的模式，用到了记录pre和cur两个指针的技巧，和这道题一样。代码如下：=根；//这个很重要，需要记录之前的节点，否则无法分配新的节点while(cur!=NULL){parent=cur;if(cur->val>val)cur=cur->left;elsecur=cur->right;}TreeNode*node=newTreeNode(val);if(valval)parent->left=node;//此时使用父节点的赋值elseparent->right=node;returnroot;}};总结一下二叉搜索树中的第一个插入操作，你不用害怕重构搜索树，事实上，你根本不需要重构。然后在递归中，我们着重介绍了如何通过递归函数的返回值来完成对新增节点及其父节点的赋值，强调了查找树的顺序。最后还是给出了迭代的方法。迭代法需要记录当前遍历节点的父节点。这和没有返回值的递归函数实现的代码逻辑是一样的。其他语言版本JavaclassSolution{publicTreeNodeinsertIntoBST(TreeNoderoot,intval){if(root==null)returnnewTreeNode(val);TreeNodenewRoot=root;TreeNodepre=root;while(root!=null){pre=root;if(root.val>val){root=root.left;}elseif(root.valval){pre.left=newTreeNode(val);}else{pre.right=newTreeNode(val);}returnnewRoot;}}递归方法classSolution{publicTreeNodeinsertIntoBST(TreeNoderoot,intval){returnbuildTree(root,val);}publicTreeNodebuildTree(TreeNoderoot,intval){if(root==null)//如果当前node如果为空，说明val找到了合适的位置，此时直接创建节点并返回。returnnewTreeNode(val);if(root.valval){root.left=buildTree(root.left,val);//递归创建左子树}returnroot;}}Python递归方法-有返回值classSolution:definsertIntoBST(self,root:TreeNode,val:int)->TreeNode:ifrootisNone:returnTreeNode(val)#如果当前节点为空，说明val已经找到合适的位置，此时创建的节点会直接返回。ifroot.valval:root.left=self.insertIntoBST(root.left,val)#递归创建右子树leftSubtreereturnroot递归方法-无返回值在函数运行时将新节点插入到应该插入的地方。nonlocalparentifnotcur:new_node=TreeNode(val)ifparent.valTreeNode:ifnotroot:returnTreeNode(val)parent=Nonecur=root#使用while循环不断寻找新节点的父节点whilecur:ifcur.valval:parent=curcur=cur.left#运行到这里表示已经跳出上面的while循环，#也表示找到了新节点的父节点。#parent已经找到，新节点为准备好。只需将两个节点粘在一起即可。ifparent.val>gt;val:parent.left=TreeNode(val)else:parent.right=TreeNode(val)returnroot
