This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

I. Title Description:

They’re saying, you’re given a binary tree, and you want to determine whether it’s symmetric along the central axis.

For example, you are given a binary tree: 1 / \ 2 2 / \ / \ 4 8 8 4 This binary tree is symmetric along the central axis, so return true. If I get rid of the last 4:1 / \ 2, 2 / \ / 4, 8, 8 is not symmetric, and I return false.Copy the code


Ii. Analysis of Ideas:

This problem is looking at tree traversal.

Ideas:

  1. Recursively determine the left and right subtrees
  2. Non-recursive: stack processing


Three,ACCode:

public class LeetCode_101 {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(intx) { val = x; }}// Recursive:
    // Time complexity: The entire tree has only two leftmost and rightmost branches
    // Time o(n), Space o(n), Faster: 100.00%
    public boolean isSymmetric(TreeNode root) {
        if (null == root) {
            return true;
        }
        return isSymmetricNode(root.left, root.right);
    }

    private boolean isSymmetricNode(TreeNode left, TreeNode right) {
        if(left ! =null&& right ! =null) {
            if(left.val ! = right.val)return false;
            return isSymmetricNode(left.left, right.right) && isSymmetricNode(left.right , right.left);
        }

        return left == null && right == null;
    }

    // Non-recursive: stack simulation
    // Time o(n), Space O (n), Faster: 28.14%
    public boolean isSymmetricNode(TreeNode root) {

        if (null == root) return true;

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root.left);
        stack.push(root.right);

        while(! stack.isEmpty()) { TreeNode rightNode = stack.pop(); TreeNode leftNode = stack.pop();if (leftNode == null && rightNode == null) continue;
            if (leftNode == null || rightNode == null) {
                return false;
            }

            if(rightNode.val ! = leftNode.val) {return false;
            }

            stack.push(leftNode.left);
            stack.push(rightNode.right);
            stack.push(leftNode.right);
            stack.push(rightNode.left);
        }
        return true; }}Copy the code


Iv. Summary:

Tree traversal template

There are four types of tree traversal:

  1. The former sequence traversal
  2. In the sequence traversal
  3. After the sequence traversal
  4. Level traversal

It can also be divided into depth-first traversal (DFS) and breadth-first traversal (BFS)

Hierarchy traversal: Is for breadth-first traversal.

Other traversal: Is for depth-first traversal.

1. Preorder traversal

void traverse(TreeNode root) {
    if (null == root) return;
    
    // Preorder traversal code
    
    traverse(root.left);
    traverse(root.right);
}
Copy the code

2. Middle order traversal

void traverse(TreeNode root) {
    if (null == root) return;
    
    traverse(root.left);
    
    // Preorder traversal code
    
    traverse(root.right);
}
Copy the code

3. Back-order traversal

void traverse(TreeNode root) {
    if (null == root) return;
    
    traverse(root.left);
    traverse(root.right);
    
    // Preorder traversal code
}
Copy the code

4. Hierarchy traversal

Queue simulation

void traverse(TreeNode root) {
    if (null == root) return;
    
    // Initialize the queue to add root to the queue
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    
    while(! q.isEmpty()) { TreeNode cur = q.poll();// Hierarchy traverses code
        System.out.println(root.val);
        
        if(cur.left ! =null) q.offer(cur.left);
        if(cur.right ! =null) q.offer(cur.right); }}Copy the code