Preface

Hello, I'm a long way from junior year to junior year. The direction is back-end and occasionally front-end. Now the main language is Java. Before a long time, I was learning some technology of web development, but I haven't done anything like data structure, algorithm and so on for a long time. I intend to pick it up and do a good job.

This period is also an opportunity to coincide with seeing the blog of Tsao Ha Road Flying, adding self-study groups, and happening to see the blogger organization organized a leetcode brushing and punching activities in the group. I also participated in this activity for a month, intending to insist on taking some time to do some topics every day, and record them through the blog.

There is currently a Github repository refresh Title (leetcode): Code Casual leetcode Title , currently a Binary Tree theme.

subject

Title Source leetcode

leetcode address: 101. Symmetric Binary Tree , difficulty: simple.

Title description (from leetcode):

Given a binary tree, check that it is mirrored symmetrical.

For example, a binary tree [1,2,2,3,4,4,3] Is symmetrical.

    1
   / \
  2   2
 / \ / \
3  4 4  3
 But here's the one [1,2,2,null,3,null,3] Is not mirror symmetric:
    1
   / \
  2   2
   \   \
   3    3
 
Advanced:
Can you solve this problem recursively and iteratively?

Problem

NO1: Recursive

Ideas: Use recursion to continuously compare left and right nodes, where left and right nodes refer to the corresponding left and right lateral or inner nodes. The recursive method contains two parameters, one is the left node and the other is the right node.

Here is a reference to the tutorial: Code Casual Recording In each of the following layers, I use different colors for pairing comparison, and the same is true for each recursive method.

Code:

public boolean isSymmetric(TreeNode root) {
    return compareLeftAndRight(root.left,root.right);
}

public boolean compareLeftAndRight(TreeNode left,TreeNode right){
    //Exit
    //Asymmetric case: 1. One node is null, the other is not. (2) The left and right node values are not equal.
    if(left == null && right != null){
        return false;
    }else if(left != null && right == null){
        return false;
    }else if(left == null && right == null ){  //Returns true directly for two nulls. This prevents null pointers from appearing on the following executions
        return true;
    }else if(left.val != right.val){
        return false;
    }

    //If the left and right values are the same, then compare the left and right subnodes below
    return compareLeftAndRight(left.left,right.right) && compareLeftAndRight(left.right,right.left);
}

In the recursion of this topic, if there is an asymmetric situation, the other situations will continue to be executed, and all nodes will be compared, which will result in unnecessary comparison. Here we adjust to identify the end by an attribute flag:

private boolean flag = true;

public boolean isSymmetric(TreeNode root) {
    compareLeftAndRight(root.left,root.right);
    return flag;
}

public void compareLeftAndRight(TreeNode left,TreeNode right){
    if(!flag){
        return;
    }
    //Exit
    //Asymmetric case: 1. One node is null, the other is not. (2) The left and right node values are not equal.
    if(left == null && right != null){ 
        flag = false;
        return;
    }else if(left != null && right == null){
        flag = false;
        return;
    }else if(left == null && right == null ){
        return;
    }else if(left.val != right.val){
        flag = false;
        return;
    }

    //If the left and right values are the same, then compare the left and right subnodes below
    compareLeftAndRight(left.left,right.right);
    if(!flag){
        return;
    }
    compareLeftAndRight(left.right,right.left);
}

That way, you can avoid other meaningless comparisons and additional recursive methods when there is asymmetry!

NO2: Iteration (Queue)

Idea: Actually, it is similar to recursive thinking, but also the left and right nodes of comparison (same as outside or inside), but here the queue is used to temporarily store the two left and right nodes to compare, two at the same time each time out of the queue, and four at the same time (each node has left and right children).

Code:

//Iteration: Using queues
public boolean isSymmetric(TreeNode root) {
    Deque<TreeNode> queue = new LinkedList<>();
    if(root == null){
        return true;
    }
    queue.offer(root.left);
    queue.offer(root.right);
    while(!queue.isEmpty()){
        //2 elements per queue
        TreeNode nodeLeft = queue.poll();
        TreeNode nodeRight = queue.poll();
        if(nodeLeft == null && nodeRight != null){
            return false;
        }else if(nodeLeft != null && nodeRight == null){
            return false;
        }else if(nodeLeft == null && nodeRight == null){
            continue;
        }else if(nodeLeft.val != nodeRight.val){
            return false;
        }

        //Enter the team in turn
        queue.offer(nodeLeft.left);
        queue.offer(nodeRight.right);
        queue.offer(nodeLeft.right);
        queue.offer(nodeRight.left);
    }
    return true;
}

Above is the first to enter the team, then to make a unified judgment, and then I wrote another judgment when joining the team. After writing it, thinking about the actual effect is not great, because at most only two pairs of nodes are judged in advance, here's what I would like to paste:

//Iteration: Using queues
public boolean isSymmetric(TreeNode root) {
    Deque<TreeNode> queue = new LinkedList<>();
    if(root == null || isNull(root.left,root.right)){
        return true;
    }
    if(!addQueue(root.left,root.right,queue)){
        return false;
    }

    while(!queue.isEmpty()){
        //2 elements per queue
        TreeNode nodeLeft = queue.poll();
        TreeNode nodeRight = queue.poll();

        if(!isNull(nodeLeft.left,nodeRight.right)){
            if(!addQueue(nodeLeft.left,nodeRight.right,queue)){
                return false;
            }
        }
        if(!isNull(nodeLeft.right,nodeRight.left)){
            if(!addQueue(nodeLeft.right,nodeRight.left,queue)){
                return false;
            }
        }

    }
    return true;
}

public boolean addQueue(TreeNode node1,TreeNode node2,Deque queue){
    if(isSymmetry(node1,node2)){
        queue.offer(node1);
        queue.offer(node2);
        return true;
    }else{
        return false;
    }
}

public boolean isNull(TreeNode leftNode,TreeNode rightNode){
    return leftNode == null && rightNode == null;
}

/**
     * Judging symmetry
     * @param left
     * @param right
     * @return true Indicates that two nodes are allowed to be queued, while false indicates asymmetry
     */
public boolean isSymmetry(TreeNode left,TreeNode right){
    if(left == null && right != null){
        return false;
    }else if(left != null && right == null) {
        return false;
    }else if(left.val == right.val){
        return true;
    }
    //        } else if (left == null & & right == null) {//The judgment needs to be extracted
    //            return true;
    //        }
    return false;
}

Reference Article

[1]. leetcode puzzle

[2]. Code Casual Record - 101. Symmetric Binary Tree

I am a long way, thank you for your patience in reading. If you have any questions, please point out that I will actively adopt them!
Welcome to my Public Number, Long Way Java, to share Java learning articles and related materials
Q Group: 851968786 We can discuss learning together
Note: Reprint is OK, you need to attach a link to the article