Binary tree practice the second bullet

One ： Binary tree node problem

（1） All nodes of binary tree

• To calculate the number of nodes in a binary tree, we can traverse the binary tree , If it is not empty, increase the size by one
• So we can write code like this ：

void TreeSize(BTNode* root,int*size)// Number of all nodes 
{
    
	if (root == NULL)
	{
    
		return;
	}
	(*size)++;
	TreeSize(root->left,size);
	TreeSize(root->right,size);
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

• Preorder traversal binary tree . If the node is empty, directly return , Otherwise it would be size++
• But we can also use the idea of divide and conquer to calculate the number of nodes in the binary tree
• Total number of nodes = The number of nodes in the left subtree + Number of right subtree nodes +1（ Plus one because the root is not empty , If the root is empty, return directly 0）
• So our code can be simplified into one line

int TreeSize(BTNode* root)
{
    
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

（2） The second fork is the tree k Layer nodes

• Computation first k The number of layer nodes continues to use the divide and conquer idea

• Number of roots k The number of nodes in the layer = Left subtree k-1 The number of nodes in the layer + Right subtree k-1 The number of nodes in the layer

• When k==1 when , Number of nodes returned 1, If the node is empty, return 0
  

• The code is as follows

int TreeKLevelSize(BTNode* root, int k)// The first k The number of layer nodes 
{
    
	if (root == NULL)
	{
    
		return 0;
	}
	if (k == 1)
	{
    
		return 1;
	}
	return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);
}

（3） Binary tree leaf node

• Let's recall the definition of leaf node
• Degree is 0 The nodes of are called leaf nodes
• How to calculate the number of leaf nodes of the whole binary tree
• by the way , Namely The number of leaf nodes in the left subtree plus the number of leaf nodes in the right subtree
• Therefore, when determining whether a node is a leaf node, you need to determine whether both the left tree node and the right tree node are empty
• If the root is NULL, Just go back to 0
• If the left and right subtree nodes are NULL, This node is a leaf node , return 1
• If the above two conditions are not satisfied, the leaf node has not been found , Continue to recursive
• The code is as follows ：

int TreeLeafSize(BTNode* root)// Number of leaf nodes 
{
    
	if (root == NULL) 
	{
    
		return 0;
	}
	else
	{
    
		if (root->left == NULL && root->right ==NULL)
		{
    
			return 1;
		}
		else
		{
    
			return (TreeLeafSize(root->left) + TreeLeafSize(root->right));
		}
	}
}

Two ： Find a binary tree node

• Finding a binary tree is slightly different from the previous writing , We need to create variables to hold our return values
• The idea is very simple , If the root is null, return null , If the value of the root is the same as the value found, the root is returned 、
• If not, look for the left subtree and the right subtree , Until an empty node is found
• And the node we found may be found very late , So you need to go back layer by layer , It is necessary to create variables to store the return value of each function call
• We create variables ret Store the return value of the left subtree , If it is not empty, it means you have found , Go straight back to ret, Don't look for the right subtree
• If ret If it is empty, we will continue to find the right subtree , And regardless of ret Why is the value returned directly
• Because if ret Returns directly for the value we find ret I found it , If not ret Namely NULL, What we finally return is NULL

BTNode* TreeFind(BTNode* root, BTDataType x)// Find a binary tree node 
{
    
	if (root == NULL)
	{
    
		return NULL;
	}
	if (root->data == x)
	{
    
		return root;
	}
	BTNode* ret=TreeFind(root->left, x);
	if (ret != NULL)
	{
    
		return ret;
	}
	ret=TreeFind(root->right, x);
	return ret;
}

3、 ... and ： Flip binary tree

• To flip a binary tree is to swap the nodes of each left and right subtree
• Examples are as follows ：
  
• The idea is not complicated , First create a new variable and save the right subtree , After that, the left subtree is flipped and assigned to the right subtree
• Then turn the right subtree over and assign it to the left subtree
• Eventually return root

BTNode* InvertTree(BTNode* root)// Flip binary tree 
{
    
	if (root == NULL)
	{
    
		return NULL;
	}
	BTNode* right = root->right;
	root->right = InvertTree(root->left);
	root->left = InvertTree(right);
	return root;
}

Four ： Judge whether two binary trees are equal

• If two binary trees are NULL, return true
• One for Null One is not for NULL, return false
• The values of the two roots are not equal , return false
• If none of the above is satisfied , Continue to judge whether the left subtree and the right subtree are equal
• Because the nodes of two binary trees are equal only when the left and right subtrees are equal , So you need to use && Connect
• Each node is the same, and then it returns true, If there is a difference, it will return false

bool isSameTree(BTNode* p, BTNode* q)// Judge whether two binary trees are equal 
{
    	
	if (p == NULL && q == NULL)
	{
    
		return true;
	}
	if (p == NULL || q == NULL)
	{
    
		return false;
	}
	if (p->data != q->data)
	{
    
		return false;
	}
	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

5、 ... and ： Determine whether to subtree

• Let's assume that neither binary tree is empty
• To determine whether a tree is a subtree of another tree , You need to traverse the tree , Whether each subtree is equal to its comparison
• Just need to use the last function to judge whether two binary trees are equal
• First, if the root is empty , Neither tree is empty , It means that the mother tree has come to the end , Go straight back to false
• If the root is not empty, compare it to another tree , If the same, return directly to true
• The left subtree and the right subtree are used for comparison , Return as long as there is the same true

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