101. Symmetric Tree (Easy)

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

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this 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:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

Solutions

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        return check(root.left, root.right);
    }

    private boolean check(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }

        boolean c1 = root1 == null && root2 != null;
        boolean c2 = root1 != null && root2 == null;

        if (c1 || c2 || root1.val != root2.val) {
            return false;
        }

        // to reach here, root1.val == root2.val

        // check out corresponding branches, be aware that we compare root.left against
        // root.right and root.right against root.left, rather than the same side branches
        // comparison.

        c1 = check(root1.left, root2.right);
        c2 = check(root1.right, root2.left);

        // only if both branches are symmetric, return true
        return c1 && c2;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""