Leetcode: Sword finger offer 26: judge whether T1 contains all topologies of T2

Title source

• leetcode

Title Description

Given two independent tree head nodes are t1 and t2, Judge t1 Does the tree contain t2 All topologies of the tree .

t1 The tree contains t2 All topologies of the tree , So back true.

struct TreeNode {
    
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {
    }
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {
    }
};


class Solution {
    
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
    

    }
};

title

Symmetry recursion

Many tree problems can be solved quickly by recursion , This series of recursive solutions contains a very powerful recursive thinking ： Symmetry recursion (symmetric recursion)

What is symmetry recursion ？ For a symmetric data structure （ This is a binary tree ） Thinking from the symmetry of the whole , Decompose the big problem into subproblems for recursion , It is not considered separately ( For example, the left subtree of a tree ), Consider both symmetrical parts at the same time ( Left and right subtrees ), To write symmetric recursive code

Topic classification

Most of the binary tree problems that can be solved recursively with symmetry are judgment problems (bool Type function ), This list of problems can be divided into the following two categories ：

1. There is no need to construct auxiliary functions . There are two situations for this kind of topic , The first is the single tree problem , And no part of the subtree is needed ( For example, the right subtree of the left subtree of the root node ), Only the symmetry of the left and right subtrees of the root node can be used for recursion ; The second is the double tree problem , That is, the topic itself requires comparing two trees , Then there is no need to construct a new function . The topics of this type are as follows ：
   • 100. Same tree
   • 226. Flip binary tree
   • 104. The maximum depth of a binary tree
   • 110. Balanced binary trees
   • 543. The diameter of a binary tree
   • 617. Merge binary tree
   • 572. The subtree of another tree
   • 965. Single valued binary trees
2. Auxiliary functions need to be constructed . This kind of problem can not be solved completely only by root node subtree symmetry , You must use some part of the subtree for recursion , That is to call the auxiliary function to compare the two partial subtrees . Formally, the main function parameter list has only one root node , The auxiliary function parameter list has two nodes . The topics of this type are as follows ：
   • 101. Symmetric binary tree
   • The finger of the sword Offer 26. The substructure of a tree

Problem solving template

The following is a template for binary tree symmetry recursion

（1） Recursion end condition ： Judgment of special circumstances

If it is a single tree problem , Generally speaking, as long as the following judgments are made

if(!root) return true/false;
if(!root->left) return true/false/ Recursive function ;
if(!root->right) return true/false/ Recursive function ;

If it is a double tree problem ( The root nodes are p,q), Generally speaking, make the following judgments ：

if(!p && !q)return true/false;
if(!p || !q)return true/false;

Of course, these are not all the cases , For example, some need to add the judgment of node value , Specific problems need to be analyzed

（2） Return value

Generally, the return value of symmetry recursion is a compound judgment statement of multiple conditions

It may be a combination of the following conditions ：

• Judgment of non empty node
• Node value comparison judgment
• ( Single tree ) Call the recursive functions of the left and right subtrees of the root node for recursive judgment
• ( Double tree ) Call the recursive functions of the left and right subtrees of the two trees to judge

Topic interpretation

》》 This topic

• Substructures cannot use root nodes only for symmetry recursion , Auxiliary functions need to be constructed , Judge whether a tree is a substructure of another tree when the root node values of two trees are the same
• If t1 The head node of a subtree and t2 The head node is the same , Start matching from these two header nodes , Every step of the match makes t1 and t2 Synchronous move , Every time you move , Just match once , In case it doesn't match , Go straight back false

class Solution {
    
    bool check(TreeNode *curr, TreeNode *B){
    
        if(B == nullptr){
    
            return true;
        }
        if(curr == nullptr || curr->val != B->val){
    
            return false;
        }
        return check(curr->left, B->left) && check(curr->right, B->right);
    }
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
    
    	 if(B == nullptr){
    
            return true;
        }
      
        return check(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};

》》104. The maximum depth of a binary tree

int height(TreeNode*root)
{
    
    if (!root)
        return 0;
    else
        return max(height(root->left), height(root->right)) + 1;
}

》》110. Judge whether a tree is a balanced binary tree

Special judgment ： An empty tree is a balanced tree
Return value ： Height difference between the left and right subtrees of the root node <=1 + The left subtree is a balanced binary tree + The right subtree is a balanced binary tree

bool isBalanced(TreeNode*&root)
{
    
    if (!root)
        return true;
    return (abs(height(root->left) - height(root->right)) <= 1) && isBalanced(root->left) && isBalanced(root->right);
}

》》965. Single valued binary trees

Single valued binary trees ： All node values are equal
Special judgment ：1、 An empty tree is a single valued binary tree 2、 If the left subtree is not empty and the value of the root node is different from that of the left child node ( That is, the root node is different from the left child node ), return false, Right subtree is the same
Return value ： The left subtree is a single valued binary tree + The right subtree is a single valued binary tree

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

》》572. Determine whether a number is a subtree of another tree

Special judgment ： If a tree is empty, it will not be established
The idea of this problem is quite special , First judge whether the two trees are the same , If they are the same, then they meet the meaning of the question ,
Then judge whether the left subtree of a tree is a subtree of another tree / Whether the right subtree of a tree is a subtree of another tree

bool isSubtree(TreeNode*root1, TreeNode*root2)
{
    
    if (!root1 || !root2)
        return false;
    if (isSameTree(root1, root2))
        return true;
    return isSubtree(root1->left, root2) || isSubtree(root1->right, root2);
}

》》leetcode：226. Flip binary tree

Special judgment ： The image flipped tree of an empty tree is still itself
Ideas ： Flip the left subtree and replace the right subtree , Flip the right subtree and replace the left subtree

TreeNode*invertTree(TreeNode*root)
{
    
    if (!root)
        return nullptr;
    TreeNode*left = invertTree(root->left);
    TreeNode*right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

》》617. Merge binary tree

Merge binary tree ： Merge two binary trees
Ideas ：
1、 Are all empty tree returns nullptr
2、 There is a null return to the root node of another tree
3、 If both are not empty, add the root node values of the two trees , Then recursively merge the left and right subtrees ( Take the first tree as the merged tree )

TreeNode*mergeTrees(TreeNode*root1, TreeNode*root2)
{
    
    if (!root1)
        return root2;
    if (!root2)
        return root1;
    if (root1 && root2)
        root1->val += root2->val;
    root1->left = mergeTrees(root1->left, root2->left);    // Recursively merge the left subtree 
    root1->right = mergeTrees(root1->right, root2->right); // Recursively merge right subtrees 
    return root1;
}

》》 The finger of the sword Offer 28. Symmetric binary tree

• Judge whether the left and right subtrees of the two trees are mirror symmetric （ You can't simply consider a certain subtree , You must see whether the two subtrees are poisonous stings at the same time ）

bool isSymmetric(TreeNode*root)
{
    
    return isMirror(root, root);
}

bool isMirror(TreeNode*p, TreeNode*q)
{
    
    if (!p && !q)
        return true;
    if (!p || !q)
        return false;
    return (p->val == q->val) && (isMirror(p->left, q->right)) && (isMirror(p->right, q->left));
}

》》leetcode：100. Same tree

• Same tree ： Compare whether the two trees are the same
• Special judgment ： If both trees are empty, they must be the same ; If only one of the two trees is empty, it must be different
• Return value ： Neither tree is empty + Same node root value + The left subtree is the same + The right subtree is the same

class Solution {
    
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
    
        if(p == NULL && q == NULL){
    
            return true;
        }
        
        if(p == NULL || q == NULL){
    
            return false;
        }
        
        if(q->val != p->val){
    
            return false;
        }

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