foreword

This is the 20th day of the May training camp. Today's training content is binary search tree.

Problem solving report

1. Force buckle 700

Original title link

700. Searching in Binary Search Trees

Topic overview

Given a binary search tree (BST) root node root and an integer value val.

You need to find the node whose node value is equal to val in the BST. Returns the subtree rooted at this node. Returns null if the node does not exist.

Problem solving ideas

Just use recursion directly.

Source code analysis

struct TreeNode* searchBST(struct TreeNode* root, int val){
    if (root == NULL) {
            return NULL;
        } else {
            if (root->val > val) {
                return searchBST(root->left, val);
            } else if (root->val < val) {
                return searchBST(root->right, val);
            } else {
                return root;
            }
        }
}

2. Force buckle 230

Original title link

230. K th Smallest Element in Binary Search Tree

Topic overview

Given a binary search tree root node root, and an integer k, please design an algorithm to find the kth smallest element (counting from 1).

Problem solving ideas

Direct in-order traversal will do.

Source code analysis

void first(struct TreeNode* root,int *ans,int *num){
    if(root==NULL){
        return ;
    }
    first(root->left,ans,num);
    ans[(*num)++]=root->val;
    first(root->right,ans,num);
}
int kthSmallest(struct TreeNode* root, int k){
    int ans[10005];
    int *len=0;
    first(root,ans,&len);
    return ans[k-1];
}

3. Force buckle 108

Original title link

108. Convert sorted array to binary search tree

Topic overview

Given an array nums of integers, where the elements are already in ascending order, please convert it into a height-balanced binary search tree.

A height-balanced binary tree is a binary tree that satisfies "the absolute value of the height difference between the left and right subtrees of each node does not exceed 1".

Problem solving ideas

The array is continuously split and filled into the nodes using a method similar to the dichotomy.

Source code analysis

struct TreeNode* build(int* nums, int left, int right)
{
    if (left > right)
    {
        return NULL;
    }

    int mid = left + (right - left) / 2;
    struct TreeNode* pRoot = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    pRoot->val = nums[mid];

    pRoot->left = build(nums, left, mid - 1);
    pRoot->right = build(nums, mid + 1, right);

    return pRoot;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize){
    return build(nums, 0, numsSize - 1);
}

4. Force buckle 1382

Original title link

1382. Balance Binary Search Tree

Topic overview

Given a binary search tree, please return a balanced binary search tree. The newly generated tree should have the same node value as the original tree. If there are multiple constructors, please return any one.

A binary search tree is said to be balanced if the height difference between the two subtrees of each node does not exceed 1.

Problem solving ideas

As long as the current tree is traversed in inorder and filled into the array, the array becomes an ordered array, and then the binary tree is constructed by the method of the previous question. Because it is similar to the dichotomy, the final tree must be a balanced tree.

Source code analysis

#define N 50000

void getSum(struct TreeNode*root,int *Sum,int *size)     //Get in-order traversal
{
    if(!root)
    {
        return;
    }
    getSum(root->left,Sum,size);
    Sum[(*size)++]=root->val;
    getSum(root->right,Sum,size);
}

struct TreeNode*BinaryCreate(int *Sum,int low,int high) //Dichotomous Thought Constructs AVL
{
    if(low>high)
    {
        return NULL;
    }
    int mid=(low+high)/2;
    struct TreeNode*root=malloc(sizeof(struct TreeNode));
    root->val=Sum[mid];

    root->left=BinaryCreate(Sum,low,mid-1);
    root->right=BinaryCreate(Sum,mid+1,high);

    return root;
}

struct TreeNode* balanceBST(struct TreeNode* root){


    int*Sum=malloc(sizeof(int)*N);
    int size=0;
    getSum(root,Sum,&size);
    return BinaryCreate(Sum,0,size-1);


}