插入二叉搜索树

void insert(struct TreeNode* root,int val)
{
    if(root)
    {
        if(root->val>val)
        {
            if(root->left)insert(root->left,val);
            else{
                struct TreeNode* newnode=(struct TreeNode*)malloc(sizeof(struct TreeNode));
                newnode->val=val;
                root->left=newnode;
            }
        }else{
            if(root->right)insert(root->right,val);
            else{
                struct TreeNode* newnode=(struct TreeNode*)malloc(sizeof(struct TreeNode));
                newnode->val=val;
                root->right=newnode;
            }
        }
    }
}
struct TreeNode* insertToBST(struct TreeNode* root, int val ) {
    if(root==NULL){
        struct TreeNode* newnode=(struct TreeNode*)malloc(sizeof(struct TreeNode));
        newnode->val=val;
        root=newnode;
    }
    insert(root, val);
    return root;
}

/**
 * #[derive(PartialEq, Eq, Debug, Clone)]
 * pub struct TreeNode {
 *     pub val: i32,
 *     pub left: Option<Box<TreeNode>>,
 *     pub right: Option<Box<TreeNode>>,
 * }
 *
 * impl TreeNode {
 *     #[inline]
 *     fn new(val: i32) -> Self {
 *         TreeNode {
 *             val: val,
 *             left: None,
 *             right: None,
 *         }
 *     }
 * }
 */
struct Solution{

}

type T = Option<Box<TreeNode>>;
use std::cmp::Ordering::{Less, Equal, Greater};

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param root TreeNode类 
        * @param val int整型 
        * @return TreeNode类
    */
    pub fn insertToBST(&self, mut root: T, val: i32) -> T {
        // write code here
        if root.is_none() {
            Some(Box::new(TreeNode::new(val)))
        } else {
            Self::insert(&mut root, val);
            root
        }
    }
    fn insert(mut node: &mut T, val: i32){
        loop {
            match val.cmp(&node.as_ref().unwrap().val) {
                Less => {
                    if node.as_mut().unwrap().left.is_none() {
                        node.as_mut().unwrap().left = Some(Box::new(TreeNode::new(val)));
                        break;
                    } else {
                        node = &mut node.as_mut().unwrap().left;
                    }
                },
                Greater => {
                    if node.as_mut().unwrap().right.is_none() {
                        node.as_mut().unwrap().right = Some(Box::new(TreeNode::new(val)));
                        break;
                    } else {
                        node = &mut node.as_mut().unwrap().right;
                    }
                },
                Equal => {
                    todo!();
                },
            };
        };
    }
}

package main
//import "fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param val int整型 
 * @return TreeNode类
*/
func insertToBST( root *TreeNode ,  val int ) *TreeNode {
    if root==nil{
        return &TreeNode{Val:val}
    }else if root.Val>val{
        root.Left=insertToBST(root.Left,val)
        return root
    }else{
        root.Right=insertToBST(root.Right,val)
        return root
    }
}

# -*- coding: utf-8 -*-


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class BT:
    def __init__(self):
        self.root = None

    def levelOrderToBT(self, nums):
        n = len(nums)

        if n > 0:
            self.root = TreeNode(nums[0])
            queue, idx = [self.root], 1

            while queue and idx < n:
                node = queue.pop(0)
                node.left = TreeNode(nums[idx]) \
                    if nums[idx] != None else None
                if node.left:
                    queue.append(node.left)
                node.right = TreeNode(nums[idx + 1]) \
                    if idx + 1 < n and nums[idx + 1] != None else None
                if node.right:
                    queue.append(node.right)
                idx += 2

        return self.root

    @staticmethod
    def levelOrder(root):
        if not root:
            return []

        res, queue = [], [root]
        while queue:
            node = queue.pop(0)
            if node:
                res.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append(None)

        while res and res[-1] == None:
            res.pop()

        return res


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @param val int整型
# @return TreeNode类
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/4900db9ddfbd43a7a9841c6a408bacf2?tpId=196&tqId=40503&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        搜索二叉树的插入，使用双指针parent、cur分别指向待插入位置的父节点和待插入位置，从根节点开始遍历二叉树，寻找插入位置
    复杂度：
        时间复杂度：O(logN)
        空间复杂度：O(1)
    """

    def insertToBST(self, root, val):
        # write code here
        if not root:
            return TreeNode(val)
        parent, cur = None, root
        while cur:
            if cur.val == val:
                return root
            elif cur.val < val:  # 插入右子树
                parent, cur = cur, cur.right
            else:  # 插入左子树
                parent, cur = cur, cur.left
        if parent.val > val:
            parent.left = TreeNode(val)
        elif parent.val < val:
            parent.right = TreeNode(val)
        return root


if __name__ == "__main__":
    sol = Solution()

    nums, val = [2, 1, 3], 4

    bt = BT()
    bt1 = bt.levelOrderToBT(nums)
    print BT.levelOrder(bt1)

    res = sol.insertToBST(bt1, val)
    print BT.levelOrder(res)

import java.util.*;

public class Solution {
    public TreeNode insertToBST (TreeNode root, int val) {
        if(root == null) 
            return null;
        TreeNode cur = root;//用于遍历
        TreeNode p = cur;//用于记录cur的位置
        while(cur != null) {
            if(cur.val > val) {
                p = cur;
                cur = cur.left;//放左边
            }else {
                p = cur;
                cur = cur.right;//放右边
            }
        }
        TreeNode node = new TreeNode(val);
        if(p.val > val) {
            p.left = node;
        }else {
            p.right = node;
        }
        return root;
    }
}

import java.util.*;

public class Solution {
    public TreeNode insertToBST (TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode head = root;
        while (true) {
            if (root.val < val) {
                if (root.right == null) {
                    root.right = new TreeNode(val);
                    break;
                }
                root = root.right;
            } else if (root.val > val) {
                if (root.left == null) {
                    root.left = new TreeNode(val);
                    break;
                }
                root = root.left;
            } else {
                break;
            }
        }
        return head;
    }
}