The topic of dry

Given two nonempty binary trees S and T, test whether S contains subtrees with the same structure and node values as T. A subtree of S consists of a node of S and all the children of that node. S can also be viewed as a subtree of itself.

Example 1: Given tree S:

      3
     / \
    4   5
   / \
  1   2
Copy the code

Given tree t:

    4 
   / \
  1   2
Copy the code

Returns true because t has the same structure and node values as a subtree of S.

Source: LeetCode link: leetcode-cn.com/problems/su… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution: Recursion

The idea of this problem is very simple. We compare each node of S with the t tree to see if the root node of S is equal to the t tree.

If we don’t return true by the time we get to the leaf, we’ll return false. Traversing the entire S-tree.

Next comes the logic by which we compare whether trees are equal to trees. First let’s look at the exit conditions. If we have root1 and root2 both as leaf nodes, we return true. If we have a non-leaf node, we have different structures. We then compare whether our left and right nodes are equal, and whether the val of the current node is equal.

Code implementation

 / * * *@param {TreeNode} root
  * @param {TreeNode} subRoot
  * @return {boolean}* /
 var isSubtree = function (root, subRoot) {
     function doFindRoot(root, subRoot) {
         if (root == null) return false
         if (doFindsubRoot(root, subRoot)) {
             return true
         }
         let a = doFindRoot(root.left, subRoot)
         let b = doFindRoot(root.right, subRoot)
         return a || b
     }
     function doFindsubRoot(root1, root2) {
         if (root1 == null && root2 == null) return true
         if (root1 == null || root2 == null) return false
         let left=doFindsubRoot(root1.left, root2.left)
         let right=doFindsubRoot(root1.right, root2.right)
         if(left&&right&&root1.val == root2.val) return true
         
     }
     return doFindRoot(root, subRoot)
 };
Copy the code