“This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

preface

The symmetric binary tree of problem 101 is shown as follows:

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

A, thinking

There’s a key piece of information in the title: mirror symmetry.

So what is mirror symmetry? Left == right. Right == right. Left == right. As shown below:

Therefore, we can start from the root node and reach the left child of the root node left and right child right. If the values are the same, we can continue to check whether left. Left is equal to right.

Since each node can be a subtree, it’s a good idea to use recursion instead of manually maintaining the stack.

In recursion we deal with some special boundary cases like this:

  1. If the root node is emptynull, directly returnstrueCan. (Empty nodes are also considered mirror symmetric.)
  2. ifleft == right == null, can also returntrue(Two empty nodes are equal)
  3. ifleft 和 rightReturns if only one is emptyfalse(Obviously empty nodes do not equal valued nodes)

For example

Let’s take the following tree as an example:

  1. Compare the child to the left of the root node, and equal continues downward

  1. Continue comparing subtreesleftTo the left of the child and child treerightThe right child, found5 != 3, indicates that the tree is not mirror symmetric

  1. When the result is found, return directlyfalseCan be

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public boolean isSymmetric(TreeNode root) {
        if(root == null)
            return true;
        return dfs(root.left, root.right);
    }

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

The test code

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1.new TreeNode(2.new TreeNode(3), new TreeNode(4)),
                new TreeNode(2.new TreeNode(4), new TreeNode(3)));
        boolean flag = new Number101().isSymmetric(treeNode);
        System.out.println(flag);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section