[tree] 101 Symmetric binary tree (preorder traversal + method optimization)

Section 101 Symmetric binary tree

Title Link: https://leetcode-cn.com/problems/symmetric-tree/

Classification: tree (binary tree), preorder traversal (recursion, iteration), algorithm optimization

Idea 1: left and right synchronous DFS (preorder traversal recursive implementation, traversal twice)

Use depth first traversal in the way of root - > left - > right and root - > right - > left respectively. Once one node is empty, the other is not empty, or the two nodes val are not equal, return false.
If the traversal is not interrupted until the end, it indicates that the binary tree is symmetrical and returns true.

The implementation code is essentially pre order traversal, but one is to traverse the left subtree first and then the right subtree; The other is to traverse the right subtree first and then the left subtree.

Implementation code

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return dfs(root, root);
    }
    //Left and right synchronous dfs, i.e. preorder traversal
    public boolean dfs(TreeNode root1, TreeNode root2){
        if(root1 == null && root2 == null) return true;//Both traversals encounter empty nodes
        if(root1 == null || root2 == null) return false;//Only one traversal encounters an empty node
        if(root1.val != root2.val) return false;//When two traversal nodes val are not equal
        return dfs(root1.left, root2.right) && dfs(root1.right, root2.left);//One enters the left subtree first, and the other enters the right subtree first
    }
}

Idea 1 Optimization: only traverse once

The method of idea 1 will lead to traversing the tree twice as a whole. Both root - > left - > right and root - > right - > left completely traverse the binary tree once respectively, but in fact, it only needs to be compared to stop when the two traversal nodes meet, because the subsequent comparison results are completely consistent with the previous ones.

Therefore, the recursive exit can be modified to:

if(root1 == root2) return true;

When two nodes meet, it means that if they meet the node on the symmetry axis of the binary tree, they can return directly without further traversal.

The starting point of traversal is also modified to the left and right of the child Left and root Right. After the above modifications are avoided, the recursive function will exit as soon as the comparison starts from root:

    dfs(root.left, root.right);

Implementation code

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        else return dfs(root.left, root.right);
    }
    //Left and right synchronous dfs, i.e. preorder traversal
    public boolean dfs(TreeNode root1, TreeNode root2){
        if(root1 == root2) return true;//When two traversal nodes meet, they directly return true and interrupt the traversal process
        if(root1 == null || root2 == null) return false;//Only one traversal encounters an empty node
        if(root1.val != root2.val) return false;//When two traversal nodes val are not equal
        return dfs(root1.left, root2.right) && dfs(root1.right, root2.left);//One enters the left subtree first, and the other enters the right subtree first
    }
}

Idea 2: left and right synchronous DFS (preorder traversal iterative implementation, traversal once)

A traversal starts from the left and right subtrees at the same time. The iterative implementation of preorder traversal, so two stacks are used for root - > left - > right and root - > right - > left preorder traversal respectively.

Framework and implementation of code Iteration of single pass preorder traversal The implementation is basically the same. The details of modification include:

1. Stack operation of traversing the nodes to be stacked in two previous sequences
Points that cannot be handled temporarily in the process of traversal into the stack, so they are stored in the stack. According to the characteristics of two traversals, the right child is traversed by the root - > left - > right, and the left child is traversed by the root - > right - > left:

    stack1.push(root1.right);
    stack2.push(root2.left);

Note that before the nodes to be processed are put into the stack, they should be compared: because these two nodes to be put into the stack are symmetrical nodes. They can be put into the stack only if they are empty at the same time, or not empty at the same time and val is equal

  • If one of the two nodes to be stacked is empty and one of them is not empty, false is returned;
  • If they are not empty, judge whether val is equal before entering the stack, because these two nodes are symmetrical nodes in the tree;
    • If val is not equal, return false immediately;
    • If val is equal, the two nodes are stacked;
      //If one of the corresponding child nodes to be stacked (root - > left - > right save right child, root - > right - > left save left child) is empty, false is returned
    if(root1.right == null && root2.left != null || (root1.right != null && root2.left == null)) return false;
    //When none is empty
    if(root1.right != null && root2.left != null){
        //If val is not equal, it will directly return false, because the two nodes are symmetrical nodes
        if(root1.right.val != root2.left.val) return false;
        //val equal to the stack
        stack1.push(root1.right);
        stack2.push(root2.left);
    }

2. After exiting the internal loop while (root1! = null & & root2! = null) and before popping up the top of the stack, one of the two current nodes may be empty and the other may not be empty. In this case, return false:

  //If one node is empty and the other node is not empty, false will be returned directly
  if((root1 == null && root2 != null) || (root1 != null && root2 == null)) return false;
For example:
       2
   3       3
 4   5  5
 The root traverses left and right to 4, and the root traverses right and left to 3.right==null When, the inner loop will exit. At this time, the two nodes are asymmetric and should be returned false. 

The optimization part is the same as the optimization of idea 1. When root1==root2, it means that the two traversals meet. You can exit the current traversal process immediately without further traversal.

Implementation code

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        else return dfs(root.left, root.right);//Start with the left and right children of the root node
    }
    //Left and right synchronous dfs, that is, preorder traversal and iterative implementation
    public boolean dfs(TreeNode root1, TreeNode root2){
        //Preprocessing of root nodes of left and right subtrees
        if(root1 == root2) return true;//When two traversal nodes meet, they directly return true and interrupt the traversal process (reducing the overall traversal calculation by half)
        if(root1 == null || root2 == null) return false;//If only one of the traversals encounters an empty node, and the other is non empty, false is returned
        if(root1.val != root2.val) return false;//When two traversal nodes val are not equal    

        Stack<TreeNode> stack1 = new Stack<>();//For root - > left - > right
        Stack<TreeNode> stack2 = new Stack<>();//For root - > right - > left

        while((!stack1.isEmpty() && !stack2.isEmpty()) || (root1 != null && root2 != null)){
            //optimization
            if(root1 == root2) return true;//When two traversal nodes meet, they directly return true and interrupt the traversal process (reducing the overall traversal calculation by half)
            if(root1 == null || root2 == null) return false;//If only one of the traversals encounters an empty node, and the other is non empty, false is returned

            //Exit the loop when one or both nodes are empty
            while(root1 != null && root2 != null){
                //If neither of the two nodes is empty, val is compared
                if(root1.val != root2.val) return false;
                
                //If one of the two traversal corresponding temporary child nodes (root - > left - > right save right child, root - > right - > left save left child) is empty, false is returned
                if(root1.right == null && root2.left != null || (root1.right != null && root2.left == null)) return false;
                //When none is empty
                if(root1.right != null && root2.left != null){
                    //If val is not equal, it will directly return false, because the two nodes are symmetrical nodes
                    if(root1.right.val != root2.left.val) return false;
                    //val equal to the stack
                    stack1.push(root1.right);
                    stack2.push(root2.left);
                }
                root1 = root1.left;
                root2 = root2.right;
            }
            //If one node is empty and the other node is not empty, false will be returned directly
            if((root1 == null && root2 != null) || (root1 != null && root2 == null)) return false;
            //Pop up the previously staged node from the stack
            if(!stack1.isEmpty() && !stack2.isEmpty()){
                root1 = stack1.pop();
                root2 = stack2.pop();
            }
        }
        return true;
    }
}

Posted by mentor on Tue, 10 May 2022 04:13:44 +0300