二叉搜索树中的插入操作

题目：

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

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

思路：

根据二叉搜索树的性质，大于根节点便放在根节点的右子树，小于根节点便放在根节点的左子树。直至找到叶子节点。

方法1：

使用迭代遍历

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* node = new TreeNode(val);
        if(NULL == root) return node;
        TreeNode* traverse_node = root, *parent = NULL;
        while(traverse_node)
        {
            parent = traverse_node;
            if(traverse_node->val > val)  traverse_node = traverse_node->left;
            else if(traverse_node->val < val) traverse_node = traverse_node->right;
        }
        if(parent->val > val) parent->left = node;
        else parent->right = node;
        return root;
    }
};

方法2：

版本1

使用先序递归遍历

class Solution {
public:
    void PreOrder(TreeNode* root, TreeNode* node, TreeNode* pre)
    {
        if(NULL == root)
        {
            if(pre->val > node->val) pre->left = node;
            else pre->right = node;
            return;
        }
        if(root->val > node->val)  PreOrder(root->left, node, root);
        else if(root->val < node->val) PreOrder(root->right, node, root);
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* node = new TreeNode(val);
        if(NULL == root) return node;
        PreOrder(root, node, NULL);
        return root;
    }
};

版本2

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if (root->val > val) root->left = insertIntoBST(root->left, val);
        if (root->val < val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};