Cabbage Java self study room covers core knowledge

Force buckles the original problem

101. Symmetric binary trees

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 3Copy the code

Their thinking

A tree is symmetric if its left subtree mirrors its right subtree.

The two trees are mirror images of each other if the following conditions are met:

  • Their two roots have the same value
  • The right subtree of each tree mirrors the left subtree of the other tree

Obviously, we can do this recursively.

  1. Compare the values of the root nodes of the left and right subtrees.
  2. Compare whether the left node of the left subtree is equal to the right node of the right subtree;
  3. Compares whether the right node of the left subtree is equal to the left node of the right subtree.

When does the recursion end?

  1. When at least one of the two root nodes is empty.
  2. When the values of the two root nodes are not equal.

Code implementation

class Solution {

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

    public boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if(left.val ! = right.val)return false;
        returnisSymmetric(left.left, right.right) && isSymmetric(left.right, right.left); }}Copy the code

Complexity analysis

  • Time complexity: The tree is traversed here and the asymptotic time complexity is O(n)O(n)O(n).

  • Space complexity: The space complexity here is related to the stack space used for recursion, where the number of recursive layers does not exceed NNN, so the progressive space complexity is O(n)O(n)O(n).