LC.701 ｜ 二叉搜索树中的插入操作 ｜ 树 ｜ 迭代模拟

输入：
二叉搜索树的根节点root和一个待插入的整数val。

要求：
将val插入到二叉搜索树中，并保证插入后整棵树仍然满足 BST 的性质（左 < 根 < 右）。
题目保证新值和原始树中任意节点值都不同。

输出：
插入节点后的二叉搜索树的根节点。

思路：

在二叉搜索树中插入新节点，其实就是**“一次失败的查找”**。我们要找这个值应该在的位置，直到走到死胡同（空指针），那个位置就是它该待的地方。

本题解采用了迭代（循环）法，相比递归不仅逻辑直观，而且空间复杂度更优。

1. 特判空树：
   如果根节点为空，直接用新值创建一个节点并返回，它就是新的根。

2. 寻找插入位置（模拟）：
   使用while循环遍历树，利用 BST 性质（val大往右走，val小往左走）。

   • 关键技巧 - “向前看一步”：
     在决定向左还是向右移动之前，先检查那边的路是不是断的（即子节点是否为null）。
     • 如果是null，说明找到了！直接new一个节点接上去，任务完成，返回根节点。
     • 如果不是null，则移动指针root继续向下寻找。

复杂度：

• 时间复杂度：O(H)
  • 树的高度。我们需要从根遍历到叶子节点。
• 空间复杂度：O(1)
  • 使用了迭代法，不需要递归栈，仅使用了常数个辅助变量。

classSolution{public:TreeNode*insertIntoBST(TreeNode*root,intval){if(!root){TreeNode*ans=newTreeNode(val);returnans;}TreeNode*ans=root;while(root){if(root->val<val){if(!root->right){TreeNode*tmp=newTreeNode(val);root->right=tmp;returnans;}else{root=root->right;}}else{if(!root->left){TreeNode*tmp=newTreeNode(val);root->left=tmp;returnans;}else{root=root->left;}}}returnans;}};