Leetcode question brushing: binary tree 26 (insertion operation in binary search tree)

701. Insert operation in binary search tree

Force button topic link

Given a binary search tree （BST） The root node of and the value to insert into the tree , Insert values into a binary search tree . Return to the root node of the binary search tree after insertion . Input data guarantee , The new value is different from any node value in the original binary search tree .

Be careful , There may be many effective insertion methods , As long as the tree remains a binary search tree after insertion . You can return any valid result .

Tips ：

• The number of nodes on a given tree is between 0 and 10^4 Between
• Each node has a unique integer value , Value range from 0 To 10^8
• -10^8 <= val <= 10^8
• The new value is different from any node value in the original binary search tree

A very simple question , Traverse in the way of binary search tree , When you encounter leaf nodes, you can directly judge the size , Add left or right... As appropriate ; Single output node encountered , First judge the size , If it is a branch without degree , Then add a new left or right node directly on this node , If it is a branch with out degree , Loop to that node and then process .

package com.programmercarl.tree;

/** * @ClassName InsertIntoBST * @Descriotion TODO * @Author nitaotao * @Date 2022/7/6 14:47 * @Version 1.0 * https://leetcode.cn/problems/insert-into-a-binary-search-tree/ * 701.  Insert operation in binary search tree  **/
public class InsertIntoBST {
    
    public TreeNode insertIntoBST(TreeNode root, int val) {
    
        // Empty root node , Just create a node and return 
        if (root == null) {
    
            return new TreeNode(val);
        }
        TreeNode node = root;
        insert(node, val);
        return root;
    }

    public void insert(TreeNode root, int val) {
    
        // The current node is a leaf node 
        if (root.left == null && root.right == null) {
    
            if (root.val > val) {
    
                // The current value is larger than the target value 
                root.left = new TreeNode(val);
            } else {
    
                root.right = new TreeNode(val);
            }
            return;
        }
        // Single output 
        if (root.left == null && root.right != null) {
    
            if (root.val > val) {
    
                // The current value is larger than the target value 
                root.left = new TreeNode(val);
                return;
            }
        }

        if (root.left != null && root.right == null) {
    
            if (root.val < val) {
    
                // The current value is smaller than the target value 
                root.right = new TreeNode(val);
                return;
            }
        }
        if (root.val > val) {
    
            // The current value is larger than the target value 
            insert(root.left, val);
        } else {
    
            insert(root.right, val);
        }
    }
}