Elementary OJ problem of binary tree

Flip binary tree

link ： Flip binary tree

Problem description

Turn over a binary tree

     4
   /   \
  2     7
 / \   / \
1   3 6   9    Input 
     4
   /   \
  7     2
 / \   / \
9   6 3   1    Output 

analysis ：
The left and right child nodes are exchanged from the bottom of the binary tree to the root node
The code is as follows ：

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

---

Symmetric binary tree

link ： Symmetric binary tree

Problem description

Given a binary tree , Check if it is mirror symmetric .

 for example , Binary tree  [1,2,2,3,4,4,3]  It's symmetrical .
    1
   / \
  2   2
 / \ / \
3  4 4  3 
 But the next one  [1,2,2,null,3,null,3]  It's not mirror symmetric :
   1
  / \
 2   2
  \   \
   3    3

Method 1 analysis ：( recursive )

1. When the left and right child nodes are empty, it returns true
2. Because it has been judged that left and right Whether all are empty , So the next step is to use ‘||’ As long as there is something blank, it will be different
3. (left->val==right->val)&&_isSymmetric(left->left,right->right)&&_isSymmetric(leftright,right->left)
   Three ( The first judgment value , The last two recursions ) Phase and judgment
4. Be careful ： It's the left child of the left child and the right child of the right child ( Mirror image )

Method 2( iteration , Advanced )（ I haven't learned at the beginning ）
The code is as follows ：

bool _isSymmetric(struct TreeNode* left,struct TreeNode* right)
{
     
   if(left==NULL&&right==NULL)
       return true;
   if(left==NULL||right==NULL)
       return false;// Because it has been judged that left and right Whether all are empty , So here we use || As long as there is something blank, it will be different 
   return (left->val==right->val)&&
   			_isSymmetric(left->left,right->right)&&
   			_isSymmetric(left->>right,right->left);
}
bool isSymmetric(struct TreeNode* root){
     
   if(root==NULL)
       return true;
   return _isSymmetric(root->left,root->right);    
}

---

Binary tree traversal （ Build a binary tree ）

link ： Binary tree traversal

expand ：
Only With empty nodes That is, in the question ‘#’ Can be traversed by the first order to establish a binary tree ,
In addition, it must be First order plus middle order or Post sequence plus middle sequence To create a unique binary tree

Problem description

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 .

analysis ：

1. Reusing the pre sequence traversal code in the tree building function just changes the printed code to root Of val Assignment and array subscript ++( Subscript addressing is not a value transfer )
2. If it is null, it returns null and subscript ++

The code is as follows ：

// Middle order traversal printing 
void InOrder(struct TreeNode* root)
{
     
   if(root==NULL)
       return;
   InOrder(root->left);
   printf("%c ",root->val);
   InOrder(root->right);
}
// Build up trees 
struct TreeNode* CreatTree(char *str,int *size)
{
     
   if(str[*size]=='#')
   {
     
       (*size)++;
       return NULL;
   }
   struct TreeNode*root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
   root->val=str[*size];
   (*size)++;
   root->left=CreatTree(str, size);
   root->right=CreatTree(str, size);
   return root;
}

---

Balanced binary trees

link ： Balanced binary trees

Problem description

Given a binary tree , Determine if it's a highly balanced binary tree .
In this question , A height balanced binary tree is defined as ： Every node of a binary tree The absolute value of the height difference between the left and right subtrees is not more than 1 .

analysis ：

1. Be careful ： This problem is different from most binary tree recursion , This question is judged from top to bottom
2. The auxiliary function is the depth function of binary tree
3. (abs(left-right)<=1)&&isBalanced(root->left)&&isBalanced(root->right); As long as there is an unbalanced binary tree, it must return false

The code is as follows ：

int _isBalanced_Depth(struct TreeNode*root)
{
     
   if(root==NULL)
       return 0;
   int left=_isBalanced_Depth(root->left);
   int right=_isBalanced_Depth(root->right);
   return left>right?left+1:right+1;
}
// This method is to judge whether the subtree is a balanced tree from top to bottom 
bool isBalanced(struct TreeNode* root){
     
   if(root==NULL)
       return true;
   int left=_isBalanced_Depth(root->left);
   int right=_isBalanced_Depth(root->right);
   return (abs(left-right)<=1)&&isBalanced(root->left)&&isBalanced(root->right); 
}

---

The subtree of another tree

link ： The subtree of another tree

Problem description

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 .

analysis ：

1. The auxiliary function is to judge the same number
2. isSubtree Functions and isSametree Function because it has been determined that left and right Whether all are empty , So the next step is to use ‘||’ As long as there is something blank, it will be different
3. stay isSubtree Function ‘||’ On the left for true You don't have to look on the right , On the left for false To the right

The code is as follows ：

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);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
     
   if(root==NULL&&subRoot==NULL)
       return true;
   if(root==NULL||subRoot==NULL)
       return false;
   if(isSameTree(root, subRoot))
       return true;
   return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
   // use   or   On the left for true Just > Don't look on the right , On the left for false To the right 
}

---