101. Symmetric Tree

Published on July 13, 2023

Question

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Algorithm

This is a binary tree question. For binary tree question, normally they are preorder, inorder and postorder traversal, some times it's level order traverse. And if harder, it should be binary tree combined with some other algorithms like DBS/BFS/DP/binary search...

For this problem, we need to know what is 'mirror' meaning. It means the value of the left of left node is equals to the value of the right of right node; and the value of the right of left node is equals to the value of the left of right node.

So we can do a traverse of two sub tree in parallel and compare their values. We know the preorder traverse is root-left-right, but we cannot do this for both sub tree, since we are comparing left of left node and the right of the right node, so we traverse one sub tree with root-left-right, and the other sub tree with root-right-left. Then the pop sequence of the node we are comparing from stack would be the same. How to do this? We are using stack so we change the order of left and right push into stack. Then their pop sequence would also changed.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        TreeNode left = root.left;
        TreeNode right = root.right;
        return traverse(left, right);
    }
    
    private boolean traverse(TreeNode left, TreeNode right) {
        Stack<TreeNode> stack = new Stack();
        Stack<TreeNode> stack2 = new Stack();
        if (left != null) stack.push(left);
        if (right != null) stack2.push(right);
        while (!stack.isEmpty() && !stack2.isEmpty()) {
            TreeNode node1 = stack.pop();
            TreeNode node2 = stack2.pop();
            if (node1 == null && node2 == null) {
                continue;
            } else if (node1 == null || node2 == null) {
                return false;
            } else if (node1.val != node2.val) {
                return false;
            }
            stack.push(node1.left);
            stack.push(node1.right);
            stack2.push(node2.right);
            stack2.push(node2.left);
        }
        return stack.isEmpty() && stack2.isEmpty();
    }
}

// recursively

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return helper(root.left, root.right);
    }
    
    private boolean helper(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        
        return helper(left.left, right.right) && helper(right.left, left.right);
        
    }
}