This is the 23rd day of my participation in the August More Text Challenge

Today is the 23rd day for me to participate in the review of August. Today, I bring you the algorithm problem about binary tree is the subtree of another tree. The text is as follows:

The title

You are given two binary trees root and subRoot. Check whether root contains a subtree with the same structure and node value as subRoot. Return true if it exists; Otherwise, return false.

A subtree of a binary tree consists of a node of the tree and all descendants of that node. Tree can also be viewed as a subtree of its own.

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2] output: trueCopy the code

Example 2:

Input: root = [3,4,5,1,2, null, null, null, null, 0], subRoot =,1,2 [4] output: falseCopy the code

Their thinking

To determine whether a tree T is a subtree of another tree S, we can determine whether t is equal to any subtree of s.

To determine whether tree T is a subtree of S, there are the following three situations:

  1. T and S are exactly the same;
  2. T is some part of the left subtree of S;
  3. T is some part of the right subtree of S;

We can use depth-first search and then enumerate each node in tree S to determine whether the subtree of that node is equal to tree T.

Code implementation

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root, subRoot);
    }

    public boolean dfs(TreeNode r, TreeNode s){
        if (r == null) {
            return false;
        }

        return check(r, s) || dfs(r.left, s) || dfs(r.right, s);
    }

    public boolean check(TreeNode r, TreeNode s){
        if (r == null && s == null) {return true;
        }

        if (r == null || s == null|| r.val ! = s.val) {return false;
        }
        returncheck(r.left, s.left) && check(r.right, s.right); }}Copy the code

The last

Complexity analysis:

  • Time complexity: for each s the point, all need to do a depth first search and t match, the matching of a time cost is O (| t |), then the total time cost is O (t | | s | | x). So the gradual time complexity is O (t | | s | | x).
  • Space complexity: Assuming that the depth of S is ds and the depth of t is dt, the maximum cost of using stack space at any time is O (Max (ds,dt)).