Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch the card for the 27th day 🎈!
🚀 Algorithm 🚀

🌲 Example of original problem

Given a binary tree, check whether it is mirror – symmetric.

For example, binary trees [1,2,2,3,4,4,3] are symmetric.

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

But the following [1,2,2,null,3,null,3] is not mirror symmetric:

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

🌻C# method: recursion

Thinking analytical

Recursion, generally speaking, a problem can be divided into several sub-problems to solve && problems and the solving process of the sub-problem is consistent with the solving process of the sub-problem && there are recursive termination conditions, meet these three conditions is suitable for recursion.

If you look directly at the example, it’s easy to see that mirror symmetry is a binary tree where each level is center-symmetric.

So you can recurse from the top level to see if each level is centrosymmetric like this.

Code:

public class Solution {
    static bool func(TreeNode x, TreeNode y) {
        if (x == null) {
            return y == null;
        }

        if (y == null|| x.val ! = y.val) {return false;
        }

        return func(x.left, y.right) && func(x.right, y.left);
    }


    public bool IsSymmetric(TreeNode root) {
        return root == null ? true: func(root.left, root.right); }}Copy the code

The execution result

By execution time:84Ms, in all CBeat 88.89% of users in # submissionMemory consumption:24.9MB, in all CBeat 91.43% of users in # commit
Copy the code

Complexity analysis

Time complexity: O(n) Space complexity: O(n)Copy the code

🌻Java Method 1: Recursion

Thinking analytical

Code:

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        returnp.val == q.val && check(p.left, q.right) && check(p.right, q.left); }}Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100.00% user memory consumption:36.5MB, beat out all Java commits37.04% of the userCopy the code

Complexity analysis

Time complexity: O(min(m+n)) where M and n are the number of nodes in two binary trees respectively. The depth-first search is performed on two binary trees at the same time. The node is accessed only when the corresponding nodes in the two binary trees are not empty. Therefore, the number of nodes accessed cannot exceed the number of nodes in the smaller binary tree. Space complexity: O(min(m+n)) where M and n are the number of nodes of two binary trees respectively. The spatial complexity depends on the number of levels of recursive calls, which do not exceed the maximum height of the smaller binary tree, which in the worst case equals the number of nodes.Copy the code

🌻Java Method 2: Iteration

Thinking analytical

In “Method 1”, we used recursive method to realize the judgment of symmetry, so how to use iterative method to achieve? First we introduce a queue, a common way to rewrite a recursive program into an iterator.

We enqueue the root node twice during initialization.

Extract two nodes at a time and compare their values (every two consecutive nodes in the queue should be equal and their subtrees mirror each other), then insert the left and right children of the two nodes into the queue in reverse order.

The algorithm ends when the queue is empty, or when we detect tree asymmetry (that is, two consecutive nodes are removed from the queue that are not equal).

Code:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i ! = m + n; ++i) { nums1[i] = sorted[i]; }}}Copy the code

The execution result

By execution time:1Ms, beat out all Java commits23.81% user memory consumption:37.8MB, beat out all Java commits7.81% of the userCopy the code

Complexity analysis

Time complexity: O() Space complexity: O(n)Copy the code

💬 summary

  • Today is the twenty-seventh day of buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!