Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Offer 26. Substructure of tree

Subject analysis

Input two binary trees A and B to determine whether B is A substructure of A. (Convention that an empty tree is not a substructure of any tree)

B is A substructure of A, that is, A has the same structure and node value as B.

For example: given tree A: 3 / \ 4 5 / \ 1 2 Given tree B: 4/1 returns true because B has the same structure and node values as A subtree of A.Copy the code

Thinking on

We need to judgeA treeDoes it includeB tree

  • So the first thing we need to do is find the root of B in A tree
  • After finding the root node of the B tree, determine whether the child node under the root node of B is equal to the child node of the node found in the A tree
  • Until the whole B tree is found in A tree, or there are different nodes

The sample

Input: A = [1,2,3], B = [3,1] output: false input: A = [3,4,5,1,2], B = [4,1] output: trueCopy the code

code

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; ** * @param {TreeNode} A * @param {TreeNode} B * @return {Boolean} */ If found, we determine whether the left and right subtrees of the node found in the tree A are the same as the left and right subtrees of the root node B. Var isSubStructure = function(A, B) {return (!! A && !! B) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)) }; var recur = function (A, B) { if (! B) return true if (! A || A.val ! == B.val) return false return recur(A.left, B.left) && recur(A.right, B.right) }Copy the code