Xiaobian has something to say: these topics are the understanding and application of the recursive traversal structure of binary tree, which are very classic topics.
After doing a few steps, you will feel that at present, you can't run away from all the problems. Recursion is just to deal with the current node - it may be to do some operations / make some judgments, which often jumps out of the condition, and then the recursive left subtree and recursive right subtree (note: the first, middle and last order changes according to the problem). And empty nodes are often the places where recursion jumps out.
Recursion seems hard to think about. At least three months ago, I didn't draw recursion expansion diagram. There are places where I feel dizzy. Now I pass it directly in my mind. I still make some progress. I feel it after doing a few. However, the time complexity of recursion, ah, can be optimized sometimes. They are all written in the article, which I still need to continue to practice.

Text begins @ does Xiaobian still love programming

🖤 Always

1. Single valued binary tree

1.1 title

Title Link: Single valued binary tree

1.2 ideas and Solutions

Divide and Conquer:

• Single valued binary tree = the values of root and left and right children are equal + the left subtree is a single valued binary tree + the right subtree is a single valued binary tree
• The smallest question with answers: empty node; The values of root and left and right children are different

bool isUnivalTree(struct TreeNode* root){
    if(root == NULL)
        return true;
    
    if(root->left && root->left->val != root->val)
        return false;

    if(root->right && root->right->val != root->val)
        return false;

    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

2. Same binary tree

2.1 title

Title Link: Same tree

2.2 ideas and Solutions

Divide and Conquer:

• Same binary tree = compare the roots of two trees + recursive left subtree (whether the left subtree of two trees is the same binary tree) + recursive right subtree (whether the right subtree of two trees is the same binary tree)

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p == NULL && q == NULL)
        return true;

    if(p == NULL || q == NULL)
        return false; // If you can get here, one of p and q must be empty
	
    // If you can get here, p and q must not be empty
    if(p->val != q->val)
        return false;

    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

This topic must be well understood. The mirror binary tree behind it is a small deformation of it; To judge whether it is a subtree of another tree, it also needs to be used as a sub function to judge whether it is equal.

3. Mirror binary tree

3.1 title

Title Link: Symmetric binary tree

3.2 ideas and Solutions

Whether it is a mirror binary tree is actually to compare whether the left and right subtrees are symmetrical. Can you feel that this is very similar to the previous question whether it is the same binary tree, but here is to compare whether the symmetrical nodes are the same.

In the original function interface, we can't recurse, so we need to write a sub function. This subfunction is a small deformation of the same binary tree.

bool _isSymmetric(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 _isSymmetric(p->right, q->left) && _isSymmetric(p->left,q->right);
}

bool isSymmetric(struct TreeNode* root){
    if(root == NULL)
        return true;

    return _isSymmetric(root->left,root->right);
}

4. A subtree of another tree

4.1 title

Title Link: A subtree of another tree

4.2 ideas and Solutions

Compare every subtree of root with sub. The subfunction of judging the same binary tree will also be used here.

Divide and Conquer:

• Is the subTree of the current node the same as the subTree + recursive left subTree + recursive right subTree
• Recursive termination condition: if the subTree of the current node is the same as the subTree, it indicates that there is a subTree

bool _isSubtree(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 _isSubtree(p->left,q->left) && _isSubtree(p->right,q->right);
}


bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    // eureka
    if(_isSubtree(root,subRoot))
        return true;

    if(root->left && isSubtree(root->left,subRoot))
        return true;
    if(root->right && isSubtree(root->right,subRoot))
        return true;
        
    return false;
}

Time complexity analysis: assume that the scale is N

Calculate the time complexity of recursion. The formula is the number of recursions * the number of recursive calls each time. Pay attention to the calculation of ideas.

• What is the time complexity of the best case? O(N).

1. It's equal as soon as it comes in
2. The roots of each subtree are not equal, so the N-th roots are compared

• What is the time complexity of the worst case? O(N^2)

Each subtree of root is compared with subRoot once, and isSameTree is different only when it is compared to the last node.

It can also be written like this——

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
   if(root == NULL)
        return false;
        
    //eureka 
    if(isSameTree(root,subRoot))
        return true;
    
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

4.3 reflection

This is very similar to finding a node with a value of x.

They are all. First compare them with the current node and return when they are equal; If it is not equal, go to the left tree to find it. If the left tree finds it, return. If the left tree does not find it, go to the right tree to find it. The only thing to compare here is not a value, but a subtree of root. Call a function to compare. Is a more complex search problem.

// The binary tree finds the node with the value of x
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;

	//Don't lose the return value of recursion, and pay attention to efficiency
	BTNode* leftRet = BinaryTreeFind(root->left, x);
	if (leftRet)
		return leftRet;

	BTNode* rightRet = BinaryTreeFind(root->right, x);
	if (rightRet)
		return rightRet;

	return NULL;  
}

5. Flip binary tree

5.1 title

Title Link: Flip binary tree

5.2 ideas and Solutions

In fact, the recursive structure of this tree is too much. In addition to experience, it still has feelings.

Divide and Conquer:

• Flip binary tree = flip the left and right chains of the current node + recursive left subtree (flip left subtree) + recursive right subtree (flip right subtree)
• Inseparable sub problem: empty node

struct TreeNode* invertTree(struct TreeNode* root){
    if(root == NULL)
        return NULL;
    
    struct TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

6. Balanced binary tree

6.1 title

Title Link: balanced binary tree

6.2 ideas and Solutions

Divide and Conquer: top-down

int TreeDepth(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    int leftDepth = TreeDepth(root->left);
    int rightDepth = TreeDepth(root->right);
    return 1 + (leftDepth > rightDepth ? leftDepth:rightDepth);
}

bool isBalanced(struct TreeNode* root){
    if(root == NULL)
        return true;

    int gap = abs(TreeDepth(root->left)-TreeDepth(root->right));
    if(gap > 1)
        return false;
    
    return isBalanced(root->left) && isBalanced(root->right);
}

Time complexity analysis O ( N 2 ) O(N^2) O(N2)

Time complexity of recursion = number of recursions * number of recursive calls

• Recursion times: isBalance traverses all nodes in the worst case N N N
• The number of calls in the recursion: finding the height of the tree TreeDepth, worst-case, and the tree degenerate into chain structure. N N N

Optimization: post order judgment - bottom-up

Time complexity: O ( N ) O(N) O(N)

bool _isBalanced(struct TreeNode* root, int* ph)
{
	if (root == NULL)
	{
		*ph = 0;//The return height of the empty tree is 0
		return true;
	}
    
	//Judge the left subtree first, and then the right subtree
	int leftHight = 0;
	if (_isBalanced(root->left, &leftHight) == false)
		return false;

	int rightHight = 0;
	if (_isBalanced(root->right, &rightHight) == false)
		return false;

	// Bring the height of the current tree to the father of the next level
	*ph = fmax(leftHight, rightHight) + 1;

	return abs(leftHight - rightHight) < 2;//Conditions of balanced binary tree
}

bool isBalanced(struct TreeNode* root)
{
	int hight = 0;
	return _isBalanced(root, &hight);
}

7. Traversal of binary tree

Title Link: Preorder traversal of binary tree
Title Link: Middle order traversal of binary tree
Title Link: Binary Tree Postorder Traversal

There is a little change between the first, middle and last order here and what we wrote ourselves, so take out the list. Let's mainly talk about the pre order, the middle order and the post order. That's the same.

It requires that the preorder traversal is stored in the array, which is from malloc.

be careful:

• Output type parameter: to return an array on Leetcode, I don't know how large the array is, and multiple return values are not allowed. Pass the address of a variable outside to you, dereference and assign value, and let the outside get it
• How large is the array? Calculate the number of nodes and open them directly at one time.
• The interface it gives cannot be recursive (do you open an array every time?), Write a sub function by yourself (adding a in front is the naming habit)
• In recursion, pay attention to the same i + +. In the last article, i emphasized this problem when talking about finding the number of nodes in the tree.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int TreeSize(struct TreeNode* root)
{
    if(root == 0)
        return 0;
    return 1 + TreeSize(root->left) + TreeSize(root->right);
}

void _preorderTraversal(struct TreeNode* root,int* a,int* pi){
    if(root == NULL)
        return ;
    // Put them into array a in turn
    a[*pi] = root-> val;
    (*pi)++;
    _preorderTraversal(root->left, a, pi);
    _preorderTraversal(root->right, a, pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int size = TreeSize(root);
    *returnSize = size;
    int* a = (int*)malloc(size*sizeof(int));
    int i = 0;
    _preorderTraversal(root, a, &i);
    return a;
}

The problems that should be paid attention to in the middle order and in the later order are the same.

Middle order traversal——

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int TreeSize(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    return 1 + TreeSize(root->left) + TreeSize(root->right);
}

void _inorderTraversal(struct TreeNode* root, int* a,int* pi)
{
    if(root == NULL)
        return ;
    _inorderTraversal(root->left, a, pi);
    a[*pi] = root->val;
    (*pi)++;
    _inorderTraversal(root->right, a, pi);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int size = TreeSize(root);
    *returnSize = size;
    int* a = (int*)malloc(size*sizeof(int));
    int i = 0;
    _inorderTraversal(root, a, &i);
    return a;
}

Postorder traversal——

int TreeSize(struct TreeNode* root)
{
    if(root == NULL)
        return NULL;
    return 1 + TreeSize(root->left) + TreeSize(root->right);
}

void _postorderTraversal(struct TreeNode* root, int* a,int* pi)
{
    if(root == NULL)
        return ;
    _postorderTraversal(root->left, a, pi);
    _postorderTraversal(root->right, a, pi);
    a[*pi] = root->val;
    (*pi)++;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int size = TreeSize(root);
    *returnSize = size;
    int* a = (int*)malloc(size*sizeof(int));
    int i = 0;
    _postorderTraversal(root, a, &i);
    return a;
}

8. Construction and traversal of binary tree THU

8.1 title

Title Link: Construction and traversal of binary tree TsingHua

8.2 ideas and Solutions

• Traverse the string in the previous order and recursively establish a binary tree
• Medium order printout
• Sequential destruction

It's wonderful to have the front, middle and back order together!

Note: when building a binary tree, the traversal string still uses output parameters, which should be familiar. The constructed tree is brought back through the return value, so there is no need to pass the secondary pointer. You can see that the interface of many topics is like this, such as the flip binary tree above.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

TreeNode* CreateTree(char* str,int* pi)
{
    if(str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = str[*pi];
    (*pi)++;
    root->left = CreateTree(str, pi);
    root->right = CreateTree(str, pi);
    return root;
}

void inorderTraversal(TreeNode* root)
{
    if(root == NULL)
        return ;
    inorderTraversal(root->left);
    printf("%c ",root->val);
    inorderTraversal(root->right);
}

void DestroyTree(TreeNode* root)
{
    if(root == NULL)
        return ;
    DestroyTree(root->left);
    DestroyTree(root->right);
    free(root);
}

int main()
{
    char str[100];
    scanf("%s",str);
    int i = 0;
    TreeNode* root = CreateTree(str, &i);
    inorderTraversal(root);
    DestroyTree(root);
    root = NULL;
    return 0; 
}