Leetcode:NO101 Symmetric binary tree

subject

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

For example, a binary tree [1,2,2,3,4,4,3] is symmetric.

    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following [1,2,2,null,3,null,3] is not mirror symmetric:

    1
   / \
  2   2
   \   \
   3    3
 
Advanced:

Can you use recursion and iteration to solve this problem?

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

Problem solving record

  • Recursion facilitates the two subtrees of the root node. The left tree accesses the left node first, and the right tree accesses the right node first. After statistics, comparison is made
  • ps, java is really annoying to deal with null
/**
 * @author ffzs
 * @describe
 * @date 2020/5/31
 */
public class Solution {
    ArrayList<Integer> left = new ArrayList<>();
    ArrayList<Integer> right = new ArrayList<>();
    public boolean isSymmetric(TreeNode root) {
        if (root==null) return true;
        LTraversal(root.left);
        RTraversal(root.right);
        if (left.size()!=right.size()) return false;
        for (int i = 0; i < left.size(); i++) {
            Integer l = left.get(i);
            Integer r = right.get(i);
            if (l == null) {
                if (r != null) return false;
            } else {
                if (r != null && !l.equals(r)) return false;
            }
        }
        return true;
    }

    private void LTraversal (TreeNode root) {
        if (root != null) {
            left.add(root.val);
            LTraversal(root.left);
            LTraversal(root.right);
        }else{
            left.add(null);
        }
    }

    private void RTraversal (TreeNode root) {
        if (root != null) {
            right.add(root.val);
            RTraversal(root.right);
            RTraversal(root.left);
        }else{
            right.add(null);
        }
    }
}

optimization

  • Compare directly in the process of recursion
/**
 * @author ffzs
 * @describe
 * @date 2020/5/31
 */
public class Solution2 {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return doubleTraversal(root.left, root.right);
    }

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

Tags: Java

Posted on Mon, 01 Jun 2020 09:21:51 -0700 by n00byboy