This is the 12th day of my participation in the August Challenge

Offer 26. Substructure of tree

The title

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.

Example 1:

Input: A = [1,2,3], B = [3,1] output: falseCopy the code

Example 2:

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

Limitations:

0 <= Number of nodes <= 10000

Methods a

DFS: Firstly, A tree is traversed sequentially, and the current node of A is taken as the follower node to determine whether it has the same structure and node value as B. If so, return true. If not, repeat the process by going to the left and right children of the current node.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    boolean dfs(TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null) return false;
        if (A.val != B.val) return false;
        return dfs(A.left, B.left) && dfs(A.right, B.right);
    }
}
Copy the code

Time complexity: O(n*n)

Space complexity: O(n)

Offer 27. Mirror of binary tree

The title

Complete a function that inputs a binary tree and outputs its mirror image.

For example, enter:

4 / \ 27 / \ / \ 1 3 6 9

Mirror output:

4 / \ 7 2 / \ / 9 6 3 1

Example 1:

Input: root = [4,2,7,1,3,6,9]Copy the code

Limitations:

0 <= Number of nodes <= 1000

Methods a

Recursion: When the recursion goes down, the sub-tree below has been mirrored, and the left and right sub-trees of the current layer are swapped.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode mirrorTree(TreeNode root) { if (root == null) return root; TreeNode left = mirrorTree(root.left); TreeNode right = mirrorTree(root.right); root.left = right; root.right = left; return root; }}Copy the code

Time complexity: O(n)

Space complexity: O(n)