Sword finger offer 26 Substructure of tree

The finger of the sword Offer 26. The substructure of a tree https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/

The essence of recursion is stack .

Recursion requires a termination condition

The traversal of binary tree mainly includes four ways , Sequence traversal 、 The former sequence traversal 、 In the sequence traversal 、 After the sequence traversal . Sequence traversal is usually called breadth first search BFS, Usually with the help of the first in first out feature of the queue , Traverse the tree layer by layer

front 、 in 、 Post order traversal belongs to depth first search , That is to say Depth FIrst Search abbreviation DFS, The processing methods of depth first search can be generally divided into recursive and non recursive methods , The non recursive way is generally stack, which is different from the breadth first queue . For the former 、 in 、 The division of post order is actually to distinguish the order of access nodes ：

  The former sequence traversal ： The root node –> The left subtree –> Right subtree

In the sequence traversal ： The left subtree –> The root node –> Right subtree

After the sequence traversal ： The left subtree –> Right subtree –> The root node

Ideas
Binary trees generally use ： recursive 、 Traversal to solve

The problem is divided into two steps ：
First step , In the tree A And trees in the forest B The value of the root node is the same as that of the node R;
The second step , Judgment tree A China and Israel R Whether the subtree of the root node contains and trees B Same structure .

Both steps can be implemented using recursion
Recursion needs to pay attention to the end condition

In the second step ,
If node R Values and trees for B The root node of is different , with R Subtrees and trees that are root nodes B Must not have the same node ;
If they have the same value , Then recursively judge whether the values of their respective left and right nodes are the same .
The termination condition of recursion is that we reach the tree A Or trees B Leaf node of .

Reference blog

Interview questions 26. The substructure of a tree （ The first sequence traversal + Include judgment , Clear illustration ） - The substructure of a tree - Power button （LeetCode）https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p/

class Solution:
    def isSubStructure(self, A, B):
        if (not A) or (not B):#A Empty or B empty 
            return False
        def contain(A,B):# Judge B Whether it is A Substructure of 
            if not B: return True#B empty 
            if not A or A.val!=B.val:return False#B Not empty ,A Empty or , Node values are different 
            return contain(A.left,B.left) and contain(A.right,B.right)
        return contain(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)