[数据结构与算法]701. 二叉搜索树中的插入操作（中等）

题目链接：701. 二叉搜索树中的插入操作

思路：拿val与根结点值比大小，看从左走还是往右走
这是添加一个叶子结点的方法；原来的结点值不发生改变
一开始思路就想错了，我还以为原二叉树的结点值还有发生交换。

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) {   //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;
    }
};