【Golang Theme learning Month 】 Brushing questions is much better than playing games. The sense of achievement is getting stronger and stronger. I insist on brushing one question every day, exercising 30 minutes every day, waiting for 8-block abs and waiting for big factory offer.

😄


  \color{red}{~}

I believe that if you encounter this problem in the interview, logical, correct expression, tear

There should be more than a few candidates.

Unfamiliar to the tree friend, can see the front of the basic training problem oh!

  • Sequential traversal in a binary tree – iteration, recursion

  • Binary tree before sequential traversal – iteration, recursion

  • Binary tree after sequential traversal – iteration, recursion

  • Sequence traversal of binary tree – iteration, recursion

  • Maximum depth of binary tree – iteration, recursion

  • Symmetric binary tree of binary tree – iteration, recursion

  • Binary tree path summation | Go theme month – iteration, recursion

  • Construct binary tree | Go theme month by traversing sequence from middle order to back order

  • Recent common ancestor of binary tree | Go theme month

  • Binary tree serialization and deserialization | Go topic month

  • Verify binary search tree | Go theme month

  • Binary search tree in search | Go subject month

Leecode 701. Insert operations in binary search trees

Inserts the value into the binary search tree (BST) given the root node and the value in the tree to be inserted. Returns the root node of the inserted binary search tree. The input data guarantees that the new value is different from any node in the original binary search tree.

Note that there may be several effective ways to insert, as long as the tree remains a binary search tree after insertion. You can return any valid result.

Example 2:

Enter: 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:,2,7,1,3,5 [4]

Reference code

Define a tree

Struct {* Val int Left *TreeNode // Left * Right *TreeNode // right node *} */Copy the code

Binary search tree, the left side is smaller than the root and the right side is larger than the root

GO language version iteration

  1. Distinguish between left and right subtrees based on the root node.

  2. If you’re in the left subtree, find out if the left subtree is empty, if it’s empty, create a tree, break out of the loop.

  3. If it’s in the right subtree, notice the right subtree of the left subtree if possible

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }
    p := root
    forp ! = nil {if val < p.Val {  / / 1.
            if p.Left == nil {  / / 2.
                p.Left = &TreeNode{Val: val}
                break
            }
            p = p.Left
        } else {   / / 3.
            if p.Right == nil {
                p.Right = &TreeNode{Val: val}
                break
            }
            p = p.Right
        }
    }
    return root
}








Copy the code

java

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode pos = root;
        while(pos ! =null) {
            if (val < pos.val) {   // Is smaller than the root node
                if (pos.left == null) {  // If the left node is empty, the target is assigned to the left node
                    pos.left = new TreeNode(val);
                    break;
                } else {    // Continue to find the left nodepos = pos.left; }}else {      // Greater than the root or left node
                if (pos.right == null) {
                    pos.right = new TreeNode(val);  
                    break;
                } else{ pos = pos.right; }}}returnroot; }}/ / recursion

public static TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) {
            return new TreeNode(val);
        }
        // Big right little left
        if(root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }else if(root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }
        return root;
    }


Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️