701.二叉搜索树中的插入操作

链接：701.二叉搜索树中的插入操作
难度：Medium
标签：树、二叉搜索树、二叉树
简介：给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

题解 1 - java

• 编辑时间：2020-02-23
• 内存消耗：41.8MB
• 编程语言：java
• 解法介绍：二分查找，若判断小则查找左节点，大则查找右节点，如果 null 则赋值。

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

题解 2 - typescript

• 编辑时间：2020-09-30
• 执行用时：128ms
• 内存消耗：45.7MB
• 编程语言：typescript
• 解法介绍：递归。

function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
  if (root === null) return new TreeNode(val);
  const v = root.val;
  if (v > val) {
    if (root.left === null) {
      root.left = new TreeNode(val);
    } else {
      insertIntoBST(root.left, val);
    }
  } else {
    if (root.right === null) {
      root.right = new TreeNode(val);
    } else {
      insertIntoBST(root.right, val);
    }
  }
  return root;
}