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

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

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

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

例如，

输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

你应该返回如下子树：

  2     
 / \   
1   3

或者这歌树也是有效的：

     5
   /   \
  2     7
 / \   
1   3
     \
      4

提示：

• 给定的树上的节点数介于0和10^4之间
• 每个节点都有一个唯一整数值，取值范围从0到 10^8
• -10^8 <= val <= 10^8
• 新值和原始二叉搜索树中的任意节点值都不同

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题根据二叉搜索树的特性，将目标值和val和root.val进行比较，找到空白地方直接插入即可

具体代码如下：

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        if (root.val > 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;
    }
}