[leetcode] [Niuke] brush questions on binary tree

Catalog

One 、 Same tree

  Two 、 Symmetric binary tree

  3、 ... and 、 Preorder traversal of two tree

  Four 、 Middle order traversal of binary trees

  5、 ... and 、 Postorder traversal of binary trees

6、 ... and 、 The subtree of another tree  

  7、 ... and 、 Traversal of binary tree

describe

Input description ：

Output description ：

---

One 、 Same tree

Here are the root nodes of two binary trees p and q , Write a function to check whether the two trees are the same .

If two trees are the same in structure , And the nodes have the same value , They are the same .

Example 1：

Input ：p = [1,2,3], q = [1,2,3]
Output ：true
Example 2：

Input ：p = [1,2], q = [1,null,2]
Output ：false
Example 3：

Input ：p = [1,2,1], q = [1,1,2]
Output ：false
 

Tips ：

The number of nodes on both trees is in the range [0, 100] Inside
-104 <= Node.val <= 104

source ： Power button （LeetCode）
link ： Power button
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

// Here our pq The nodes are binary trees that we need to judge whether they are identical 
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
// If both of our trees are empty , We think this is the same binary tree 
    if(p==NULL&&q==NULL)
    {
        return true;
    }
// Pass the first one above if Judge , When you run here again , We know that two trees cannot be empty at the same time .
// Then we need to judge whether there is an empty tree in the two trees , If there is an empty tree , Is not the same binary tree 
    if(p==NULL||q==NULL)
    {
        return false;
    }
// Determine whether the data of the nodes of our tree are the same 
    if(p->val!=q->val)
    {
        return false;
    }
// Because as long as one node is different , Our two trees are different , So we use recursion here 
// Traverse the left and right subtrees of our current root node , And then carry on and operate , Get our judgment 
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

  Two 、 Symmetric binary tree

Give you the root node of a binary tree root , Check whether it is axisymmetric .

Example 1：

Input ：root = [1,2,2,3,4,4,3]
Output ：true
Example 2：

Input ：root = [1,2,2,null,3,null,3]
Output ：false
 

Tips ：

The number of nodes in the tree is in the range [1, 1000] Inside
-100 <= Node.val <= 100

source ： Power button （LeetCode）
link ： Power button
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

// Here we directly call the code in our previous question to judge whether two binary trees are the same , But you need to change the pointer to .
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL)
    {
        return true;
    }
    if(p==NULL||q==NULL)
    {
        return false;
    }
    if(p->val!=q->val)
    {
        return false;
    }
// Because what we need to judge is whether the binary tree is symmetric , So we need to judge whether the left pointer of the left subtree and the right pointer of our right subtree point to the same subtree 
// And whether the right node of our left subtree and the left node of the right subtree point to the same subtree 
    return isSameTree(p->left,q->right)&&isSameTree(p->right,q->left);
}
// Call the above function , Then pass in the left and right pointers of our root node 
bool isSymmetric(struct TreeNode* root){
    if(root==NULL)
    {
        return true;
    }
    return isSameTree(root->left,root->right);
}

  3、 ... and 、 Preorder traversal of two tree

Give you the root node of the binary tree root , Of its node value   Before the order   Traverse .

Example 1：

Input ：root = [1,null,2,3]
Output ：[1,2,3]
Example 2：

Input ：root = []
Output ：[]
Example 3：

Input ：root = [1]
Output ：[1]
Example 4：

Input ：root = [1,2]
Output ：[1,2]
Example 5：

Input ：root = [1,null,2]
Output ：[1,2]
 

Tips ：

The number of nodes in the tree is in the range [0, 100] Inside
-100 <= Node.val <= 100

source ： Power button （LeetCode）
link ： Power button
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

// Here is the code we traverse in the previous sequence . Note that because we are at different levels of recursion , Different levels of right i Adjustment of 
// All need to be synchronized , So we use the method of value passing and calling 
void preorder(struct TreeNode* root, int* a,int* i)
{
    if(root==NULL)
    {
        return;
    }
    a[(*i)++]=root->val;
    preorder(root->left,a,i);
    preorder(root->right,a ,i);
}

// Here we initialize an array , And create pointers to different positions of the array , Then call our method above , And return our newly generated array 
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    * returnSize=0;
    int *a=malloc(sizeof(int)*2000);
    preorder(root, a,returnSize);
    return a;
}

  Four 、 Middle order traversal of binary trees

Given the root node of a binary tree root , return its Middle preface   Traverse .

Example 1：

Input ：root = [1,null,2,3]
Output ：[1,3,2]
Example 2：

Input ：root = []
Output ：[]
Example 3：

Input ：root = [1]
Output ：[1]
 

Tips ：

The number of nodes in the tree is in the range [0, 100] Inside
-100 <= Node.val <= 100

source ： Power button （LeetCode）
link ： Power button
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The middle order traversal operation only needs to modify the traversal order of the previous order traversal operation , And traverse the name  

 void inorder(struct TreeNode* root, int* a,int* i)
{
    if(root==NULL)
    {
        return;
    }
    inorder(root->left,a,i);
    a[(*i)++]=root->val;
    inorder(root->right,a ,i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    * returnSize=0;
    int *a=malloc(sizeof(int)*2000);
    inorder(root, a,returnSize);
    return a;
}

  5、 ... and 、 Postorder traversal of binary trees

Give you the root node of a binary tree root , Returns the After the sequence traversal .

Example 1：

Input ：root = [1,null,2,3]
Output ：[3,2,1]
Example 2：

Input ：root = []
Output ：[]
Example 3：

Input ：root = [1]
Output ：[1]
 

Tips ：

The number of nodes in the tree is in the range [0, 100] Inside
-100 <= Node.val <= 100

source ： Power button （LeetCode）
link ： Power button
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The post order traversal operation only needs to modify the traversal order of the above middle order traversal operation , And traverse the name   

void posorder(struct TreeNode* root, int* a,int* i)
{
    if(root==NULL)
    {
        return;
    }
    posorder(root->left,a,i);
    posorder(root->right,a ,i);
    a[(*i)++]=root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    * returnSize=0;
    int *a=malloc(sizeof(int)*2000);
    posorder(root, a,returnSize);
    return a;
}

6、 ... and 、 The subtree of another tree  

Here are two binary trees root and subRoot . test root Whether and subRoot Subtrees with the same structure and node values . If there is , return true ; otherwise , return false .

Binary tree tree A subtree of includes tree A node of and all descendants of this node .tree It can also be seen as a subtree of its own .

Example 1：

Input ：root = [3,4,5,1,2], subRoot = [4,1,2]
Output ：true
Example 2：

Input ：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output ：false
 

Tips ：

root The number of nodes on the tree ranges from [1, 2000]
subRoot The number of nodes on the tree ranges from [1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

source ： Power button （LeetCode）
link ： Power button
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

// Here we still call the code in question 1 to judge whether the two binary trees are the same .
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL)
    {
        return true;
    }
    if(p==NULL||q==NULL)
    {
        return false;
    }
    if(p->val!=q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

// We traverse our binary tree by preorder traversal , Then for each node , We will all judge 
// Whether the binary tree with this node as the root node is the same as our subtree 
// Be careful , Here we recursively call our left subtree and right subtree when we return , And return in the form of or 
// Because in our left subtree and right subtree , As long as we have a subtree in it , The result of the whole recursion should be true
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if (root==NULL)
    {
        return false;
    }
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

  7、 ... and 、 Traversal of binary tree

describe

Make a program , Read in a string of traversal strings entered by the user , Build a binary tree based on this string （ Store... As a pointer ）. For example, the following pre order traversal string ： ABC##DE#G##F### among “#” It's a space , The space character represents an empty tree . After the binary tree was established , Then the binary tree is traversed in middle order , Output traversal results .

Input description ：

Input includes 1 Line string , Length not exceeding 100.

Output description ：

There may be multiple sets of test data , For each set of data , Output the sequence traversed in the middle order after establishing the binary tree of the input string , There is a space after each character . Each output takes up one line .

Cattle from ： Binary tree traversal _ Niuke Tiba _ Cattle from

The problem is that we The realization of binary tree （C Language data structure ）_wolfwalker The blog of -CSDN Blog   Some functions in the blog are extracted .

In the above blog post , The creation of our binary tree specifies the string , What this problem needs is to input the string manually , We just need to extract the relevant content from our above blog posts , Then make some input and output changes , You can complete the topic .

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType _data;
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    assert(node);

    node->_data = x;
    node->_left = NULL;
    node->_right = NULL;

    return node;
}

BTNode* BinaryTreeCreate(char* a,int* pi)
{

    if(a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode *dst= BuyNode(a[*pi]);
    (*pi)++;

    dst->_left = BinaryTreeCreate(a,pi);
    dst->_right = BinaryTreeCreate(a,pi);
    return dst;
}

void BinaryTreeInOrder(BTNode* root)
{
    if(root == NULL)
    {
        return;
    }
    BinaryTreeInOrder(root->_left);
    printf("%c ",root->_data);
    BinaryTreeInOrder(root->_right);
}

int main()
{
// Because our title says that our array length will not exceed 100, So we create a 100 Array of 
// Then use our scanf Our input data is passed into 
    char a[100]={};
    scanf("%s",a);
    int b=0;
    int *pi=&b;

    BTNode *Btree=BinaryTreeCreate(a, pi);
    BinaryTreeInOrder(Btree);
    return 0;
}