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

Today is the third day of August, the topic brought today is the solution of symmetric binary tree, the text is as follows.

Topic:

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

Example:

Analysis of ideas:

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

So when are two trees mirror images of each other?!

We can define trees that are mirror images of each other:

  1. Their root nodes have the same value
  2. The right subtree of each tree mirrors the left subtree of the other tree

So the first thing we thought about was doing it recursively.

We call the left subtree of the root node left and the right subtree right. Traverse the tree by moving two Pointers synchronously, comparing whether left equals right, and returning if not. If so, compare the left node with the right node, and then compare the left node with the left node.

Recursive 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 isSymmetric(TreeNode root) {
        // Call a recursive function to compare left and right nodes
        return isSame(root, root);
    }

    public boolean isSame(TreeNode p, TreeNode q) {
        // The recursion terminates if both nodes are empty
        if (p == null && q == null) {
            return true;
        }
        // Or one of the two nodes is empty
        if (p == null || q == null) {
            return false;
        }
        // The values of the two nodes are equal
        // Recursively compare the left child of the left node with the right child of the right node
		// Compare the right child on the left node with the left child on the right node
        returnp.val == q.val && isSame(p.left, q.right) && isSame(p.right, q.left); }}Copy the code

In addition to using the recursive way, we can also use the iterative way to achieve symmetric binary tree.

Recall the implementation of recursion:

When the root nodes of two subtrees are equal, the left of the left subtree is compared with the right of the right subtree. This comparison is implemented recursively.

Now we use queue to implement, the idea is as follows:

  1. Start by comparing two nodes (left and right) from the queue
  2. Queue left left nodes and right right nodes
  3. Queue left right nodes and right left nodes

Iteration implement

class Solution {
	public boolean isSymmetric(TreeNode root) {
		if(root==null || (root.left==null && root.right==null)) {
			return true;
		}
		// Use queues to save nodes
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		// Put the left and right children of the root node into the queue
		queue.add(root.left);
		queue.add(root.right);
		while(queue.size()>0) {
			// Take two nodes from the queue and compare them
			TreeNode left = queue.removeFirst();
			TreeNode right = queue.removeFirst();
			// Continue the loop if both nodes are empty, and return false if either node is empty
			if(left==null && right==null) {
				continue;
			}
			if(left==null || right==null) {
				return false;
			}
			if(left.val! =right.val) {return false;
			}
			// Queue the left child of the left node and the right child of the right node
			queue.add(left.left);
			queue.add(right.right);
			// Queue the right child of the left node and the left child of the right node
			queue.add(left.right);
			queue.add(right.left);
		}
		
		return true; }}Copy the code

The last

Complexity analysis

Recursive solution: Suppose there are n nodes in the tree.

Time complexity: The tree is traversed here, and the asymptotic time complexity is O(n). Space complexity: The space complexity here is related to the stack space used for recursion. Here, the number of recursive layers does not exceed NN, so the progressive space complexity is O(n).

Iterative solution:

Time complexity: O(n). Space complexity: a queue is needed to maintain nodes. Each node enters and exits the queue at most once, and the queue does not exceed n points at most. Therefore, the progressive space complexity is O(n).