LeetCode - Medium - 701. Insert into a Binary Search Tree

阳光穿透心脏的1/2处 2022-10-07 12:46 140阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/insert-into-a-binary-search-tree/][https_leetcode.com_problems_insert-into-a-binary-search-tree]

You are given the `root` node of a binary search tree (BST) and a `value` to insert into the tree. Return the root node of the BST after the insertion. It is **guaranteed** that the new value does not exist in the original BST.

**Notice** that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return **any of them**.

**Example 1:**  
![be940ab2e07119dcd45e5d58370fc5de.png][]

Input: root = [4,2,7,1,3], val = 5
    Output: [4,2,7,1,3,5]
    Explanation: Another accepted tree is:

![343ecc534e20d94866d953b0d107f198.png][]

**Example 2:**

Input: root = [40,20,60,10,30,50,70], val = 25
    Output: [40,20,60,10,30,50,70,null,null,25]

**Example 3:**

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
    Output: [4,2,7,1,3,5]

**Constraints:**

*  The number of nodes in the tree will be in the range  \[ 0 , 1 0 4 \] \[0, 10^4\] \[0,104\].
 *  `-108 <= Node.val <= 108`
 *  All the values `Node.val` are **unique**.
 *  `-108 <= val <= 108`
 *  It’s **guaranteed** that `val` does not exist in the original BST.

## Analysis ##

方法一：递归法。

方法二：迭代法。

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class InsertIntoABinarySearchTree { 
        //方法一：递归法
    	public TreeNode insertIntoBST(TreeNode root, int val) { 
    		if(root == null)
    			return new TreeNode(val);
        	
        	if(val < root.val) { 
        		root.left = insertIntoBST(root.left, val);
        	}else if(root.val < val){ 
        		root.right = insertIntoBST(root.right, val);
        	}
        	
        	return root;
        }
        
    	//方法二：迭代法
        public TreeNode insertIntoBST2(TreeNode root, int val) { 
        	if(root == null)
        		return new TreeNode(val);
        	
        	TreeNode curr = root;
        	
        	while(true) { 
        		 if(val < curr.val) { 
        			 if(curr.left != null) { 
        				 curr = curr.left;
        			 }else { 
        				 curr.left = new TreeNode(val);
        				 break;
        			 }
        		 }else if(curr.val < val) { 
        			 if(curr.right != null) { 
        				 curr = curr.right;
        			 }else { 
        				 curr.right = new TreeNode(val);
        				 break;
        			 }
        		 }
        	}
        	
        	return root;
        }
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class InsertIntoABinarySearchTreeTest { 
    
    	@Test
    	public void test() { 
    		InsertIntoABinarySearchTree obj = new InsertIntoABinarySearchTree();
    
    		TreeNode original1 = BinaryTree.integers2BinaryTree(4,2,7,1,3);
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(4,2,7,1,3,5);
    		assertTrue(BinaryTree.equals(obj.insertIntoBST(original1, 5), expected1));
    
    		TreeNode original2 = BinaryTree.integers2BinaryTree(40,20,60,10,30,50,70);
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(40,20,60,10,30,50,70,null,null,25);
    		assertTrue(BinaryTree.equals(obj.insertIntoBST(original2, 25), expected2));
    
    		TreeNode original3 = BinaryTree.integers2BinaryTree(4,2,7,1,3,null,null,null,null,null,null);
    		TreeNode expected3 = BinaryTree.integers2BinaryTree(4,2,7,1,3,5);
    		assertTrue(BinaryTree.equals(obj.insertIntoBST(original3, 5), expected3));
    	}
    	
    	@Test
    	public void test2() { 
    		InsertIntoABinarySearchTree obj = new InsertIntoABinarySearchTree();
    		
    		TreeNode original1 = BinaryTree.integers2BinaryTree(4,2,7,1,3);
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(4,2,7,1,3,5);
    		assertTrue(BinaryTree.equals(obj.insertIntoBST2(original1, 5), expected1));
    		
    		TreeNode original2 = BinaryTree.integers2BinaryTree(40,20,60,10,30,50,70);
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(40,20,60,10,30,50,70,null,null,25);
    		assertTrue(BinaryTree.equals(obj.insertIntoBST2(original2, 25), expected2));
    		
    		TreeNode original3 = BinaryTree.integers2BinaryTree(4,2,7,1,3,null,null,null,null,null,null);
    		TreeNode expected3 = BinaryTree.integers2BinaryTree(4,2,7,1,3,5);
    		assertTrue(BinaryTree.equals(obj.insertIntoBST2(original3, 5), expected3));
    	}
    }

[https_leetcode.com_problems_insert-into-a-binary-search-tree]: https://leetcode.com/problems/insert-into-a-binary-search-tree/
[be940ab2e07119dcd45e5d58370fc5de.png]: /images/20221005/15584410003d4f73869dd5bd65d5c564.png
[343ecc534e20d94866d953b0d107f198.png]: /images/20221005/d5e52f6383d646f9b47faddc6a4d67b6.png