This is the 21st day of my participation in Gwen Challenge

Topic describes

Symmetric binary tree

Given a binary tree, check whether it is mirror – symmetric. Leetcode-cn.com/problems/sy…

For example, binary trees [1.2.2.3.4.4.3] is symmetric.1
   / \
  2   2/ \ \3  4 4  3But the following [1.2.2.null.3.null.3] is not mirror symmetric:1
   / \
  2   2
   \   \
   3    3
Copy the code

The label

recursive

Analysis of the problem solving

1. The recursion

Let’s get right to it.

This problem is easy to solve recursively. First of all, let's figure out how to establish symmetry.1
   / \
  2   2/ \ \3  4 4  3


1.Left. Val is equal to right. Val2.The left and right child nodes exist and have equal values3.The last child node isnullWe can just recurse. As shown above,1For the top of the tree, don't bother. Then you need to determine whether the left and right nodes under the tree are there,1.If the left and right nodes are equal, the two nodes do not exist, which is also symmetric and can be returned directlytrue, because there is no child node, just a tree top.2.If one of the left and right nodes does not exist it is equal to0", then go straight backfalseOn the line, because they are not symmetrical, the next face nodes do not have to see.3.The last judgment condition is that if the values of the left and right nodes are equal and exist, the child nodes under the recursive node judge the above three conditions.4.Find out if the final result is symmetric. Let's just look at the code.Copy the code

Go to ！！！！！

/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
 // A recursive helper function that takes left and right nodes.
const helper = (left: TreeNode | null, right: TreeNode | null) = > {
    // If neither left nor right node is passed, it is also a mirror
    if(left == right) return true 
    // If one of the left and right nodes does not exist, the two nodes are not symmetric
    else if (left.val === 0 || right.val === 0) return false 
    // If both left and right nodes exist and have equal values, recurse their children.
    return (left.val === right.val) && (helper(left.left, right.right)) && (helper(left.right, right.left))
}
function isSymmetric(root: TreeNode | null) :boolean {
    // The root passed in May be null.
    if(root === null || root === undefined) return true 
    else {
        
        return helper(root.left, root.right)
    }
};

Copy the code

The last

From today on, an algorithm problem and publish articles every day, first want to solve the problem group for Top100, the twelfth topic finished!!