一，二叉搜索树中的搜索
700. 二叉搜索树中的搜索 - 力扣（LeetCode）
1，递归
二叉搜索树满足如下性质：
左子树所有节点的元素值均小于根的元素值；
右子树所有节点的元素值均大于根的元素值。
据此可以得到如下算法：
若 root 为空则返回空节点；
若 val=root.val，则返回 \textit{root}root；
若 val<root.val，递归左子树；
若 val>root.val，递归右子树。
class Solution { public: TreeNode *searchBST(TreeNode *root, int val) { if (root == nullptr) { return nullptr; } if (val == root->val) { return root; } return searchBST(val < root->val ? root->left : root->right, val); } };
复杂度分析
时间复杂度：O(N)，其中 N 是二叉搜索树的节点数。最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下我们需要递归 N 次。
空间复杂度：O(N)。最坏情况下递归需要 O(N) 的栈空间。
2，迭代
我们将方法一的递归改成迭代写法：
若 root 为空则跳出循环，并返回空节点；
若 val=root.val，则返回root；
若 val<root.val，将 root 置为 root.left；
若 val>root.val，将 root 置为 root.right。
class Solution { public: TreeNode *searchBST(TreeNode *root, int val) { while (root) { if (val == root->val) { return root; } root = val < root->val ? root->left : root->right; } return nullptr; } };
复杂度分析
时间复杂度：O(N)，其中 NN 是二叉搜索树的节点数。最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下我们需要迭代 N 次。
空间复杂度：O(1)。没有使用额外的空间。
二，二叉搜索书中的插入操作
701. 二叉搜索树中的插入操作 - 力扣（LeetCode）
1，模拟
思路与算法
首先回顾二叉搜索树的性质：对于任意节点 root 而言，左子树（如果存在）上所有节点的值均小于root.val，右子树（如果存在）上所有节点的值均大于 root.val，且它们都是二叉搜索树。
因此，当将val 插入到以 root 为根的子树上时，根据val 与 root.val 的大小关系，就可以确定要将 val 插入到哪个子树中。
如果该子树不为空，则问题转化成了将 \textit{val}val 插入到对应子树上。
否则，在此处新建一个以 \textit{val}val 为值的节点，并链接到其父节点 root 上。
class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == nullptr) { return new TreeNode(val); } TreeNode* pos = root; while (pos != nullptr) { if (val < pos->val) { if (pos->left == nullptr) { pos->left = new TreeNode(val); break; } else { pos = pos->left; } } else { if (pos->right == nullptr) { pos->right = new TreeNode(val); break; } else { pos = pos->right; } } } return root; } };
复杂度分析
时间复杂度：O(N)，其中 N 为树中节点的数目。最坏情况下，我们需要将值插入到树的最深的叶子结点上，而叶子节点最深为 O(N)。
空间复杂度：O(1)。我们只使用了常数大小的空间。
