[Binary tree 2.1] Leetcode101. Symmetric binary trees (similar to flipped binary trees, but different)

The article directories

• • • Problem: 101. Symmetric binary trees
    • Solution 1: Recursion
    • • Recursive trilogy
      • Recursive algorithm (two back-order traversals)
    • Solution 2: Iterative method
    • Solution 3: Use a stack
    • conclusion

Problem: 101. Symmetric binary trees

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

Core: judge the symmetric binary tree to compare is which two nodes, not the left and right nodes to compare! In other words, whether the binary tree is symmetric or not, what we need to compare is whether the left and right subtrees of the root node flip each other. To understand this, we know that “in fact, we need to compare two trees (these two trees are the left and right subtrees of the root node)”, so in the recursive traversal process, we also need to traverse two trees at the same time.

So how do you compare?

The comparison is whether the inside and outside elements of two subtrees are equal. So what’s the order of traversal?

In this case, traversal can only be “back-order traversal”, because we need to determine whether the inner and outer nodes of two subtrees are equal by the return value of the recursive function.

“It is precisely because you are traversing two trees and comparing the inner and outer nodes that one tree is traversed in left-right order and one tree is traversed in right-left order.”

But it’s all understood as a post-order traversal, even though it’s not strictly a post-order traversal on a tree.

Solution 1: Recursion

Recursive trilogy

First, determine the parameters and return values of the recursive function

Since we want to compare the two subtrees of the root node to see if the tree is symmetric, we want to compare two trees, and the parameters are naturally the left and right subtrees of the root node.

The return value is of type bool, which is the return value of the entire Solution. True means equal, false means unequal.

The code is as follows:

public boolean compare(TreeNode left,TreeNode right)
Copy the code

Second, determine termination conditions

To compare two nodes with different values, first make it clear that the two nodes are empty! Otherwise we’ll be manipulating null Pointers later when we compare values.

When the node is empty :(” note that we are not actually comparing left and right children, so I call it left and right nodes as follows “)

1. The left node of the root node is empty, the right node is not empty, asymmetric, return false
2. The root node is not empty on the left, but empty on the right, asymmetrically return false
3. The root node is empty left and right, symmetric, and returns true

At this point, the null node case has been excluded, so what remains is that the left and right nodes are not empty:

Return false if the value of each node is different

We also dealt with the case where the left and right nodes are not empty and have different values.

The code is as follows:

if (left==null && right==null) return true;
if(left! =null && right==null)return false;
if(left==null && right! =null)return false;
if(left.val ! = right.val)return false;
Copy the code

Note the last case above, where we use if instead of returning false, because we are left with the fifth case where the left and right nodes are not empty and have the same value.

Third, determine the logic of a single layer recursion

This is when we enter the logic of single-layer recursion, which is to deal with the case where the right nodes are not empty and the value is the same, which is the fifth case.

1. Compare the lateral symmetry of binary trees: the left child of the left node is passed in, the right child of the right node is passed in.
2. To compare whether the internal test is symmetric, pass the right child of the left node, the left child of the right node.

Return true if both sides are symmetrical and false if one side is asymmetric.

The code is as follows:

boolean outSide = compare(left.left,right.right); Boolean inSide = compare(left. Right,right. Left); Boolean inSide = compare(left. boolean isSame = outSide && inSide;return isSame;
Copy the code

Because it’s a binary tree, not an n-tree, so if you compare left and right nodes, an n-tree is going to compare 1 to N children

In the code above, we can see that the traversal method used is left-right center for the left subtree and right-left center for the right subtree, so I also call this traversal order “post-order traversal” (although not strictly post-order traversal).

Recursive algorithm (two back-order traversals)

class Solution {
    public boolean isSymmetric(TreeNode root) {
       if (null == root) return true; // Handle empty casesreturn compare(root.left,root.right);
    }
    public boolean compare(TreeNode left,TreeNode right){
        if (left==null && right==null) return true;
        if(left! =null && right==null)return false;
        if(left==null && right! =null)return false;
        if(left.val ! = right.val)return false;
        boolean outSide = compare(left.left,right.right);
        boolean inSide = compare(left.right,right.left);
        boolean isSame = outSide && inSide;
        returnisSame; }}Copy the code

Solution 2: Iterative method

We can also use the iterative method for this problem, but note that this is not the iterative method, because the essence of this problem is to determine whether two trees are reversed, in fact, not the so-called binary tree traversal relationship.

Here we can use queues to compare whether two trees (left and right subtrees of the root node) flip each other (” Note that this is not sequential traversal “).

Use queues to determine whether the inside and outside sides of the left and right subtrees of the root node are equal, as shown in the animation:

The picture

The following conditional judgment is the same logic as recursion.

The code is as follows:

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (null == root) return true;
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root.left);
        queue.offer(root.right);
        while(! queue.isEmpty()) { TreeNode left = queue.poll(); TreeNode right = queue.poll(); // Two at a timeif (left == null && right == null) continue; // There is no return heretrueRecursively, it works, but iteratively, it doesn'ttrueAnd the whole Solution endsif(left ! = null && right == null)return false; / / 3falseInstead, you can just go back and end the Solutionif(left == null && right ! = null)return false;
            if(left.val ! = right.val)return false; Node. left and node.right are not null, so queue.offer(left. Left) is not null; queue.offer(right.right); Queue.offer (left. Right); queue.offer(right.left); // Add inner node}return true; // If you can get out, go backtrueSymmetric}}Copy the code

Solution 3: Use a stack

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (null == root) return true;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root.left);
        stack.push(root.right);
        while (!stack.isEmpty()) {
            TreeNode left = stack.pop();  // top element of stack
            TreeNode right = stack.pop();  // Two at a time
            if (left == null && right == null) continue;  // We can't return true for recursion, but not for iteration, so return true and the whole Solution is over
            if(left ! = null && right == null)return false;
            if(left == null && right ! = null)return false;
            if(left.val ! = right.val)return false;  Node. left and Node. right are not null, so there is no null pointer
            stack.push(left.left);
            stack.push(right.right);  // Add the outer node
            stack.push(left.right);
            stack.push(right.left);  // Add the inner node
        }
        return true; // Return true symmetry if it can walk out}}Copy the code

conclusion

This time we have made an in-depth analysis of the “simple problem” of a binary tree. We will find that it is not easy to really make the problem clear. There is still a distance between accepting on Leetcode and really mastering it.

We introduced recursion and iteration, and recursion still solves the problem through a recursive trilogy, which you can’t tell by looking at the simplified code.

In the iterative method we use queues. It is important to note that this is not sequential traversal, and only pairs of elements are stored by a container. Knowing the nature of this, it is possible to use queues, stacks, and even arrays.