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
Example 2:
Input: root = [1,2,2,null,3,null,3] Output: false
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]. -100 <= Node.val <= 100
Follow up: Could you solve it both recursively and iteratively?
Solution
Key thing to observe here (which I missed initially) is that we need to find out if this binary tree is cut into half at the center and if left half is shown in the mirror, the mirror image should be equivalent to right half. See the central line in example one and visualize that in your mind.
Once it got clear to me about the problem, I started thinking about the solution. For any binary tree problem, my first thought process is always Can I solve it through recursion? On first try I could not solve it. I saw a hint and then got one important thing here to keep in mind. That around the center left and right child should be equal. And then left’s right child should be equal to right’s left child. And left’s left child should equal to right’s right child. We can now implement this recursively.
Below is the Java code for the same.
/**
* 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) {
return root == null || isSymmetricFun(root.left, root.right);
}
private boolean isSymmetricFun(TreeNode left, TreeNode right) {
if (left == null || right == null) return left == right;
else if (left.val != right.val) return false;
else return isSymmetricFun(left.left, right.right) && isSymmetricFun(left.right, right.left);
}
}Once I checked on efficiency for the same on LeetCode I saw the following results.
For binary tree problems, recursion can be thought as one of viable and easy to understand solutions. If you are able to derive right recursion function with right input parameters you have almost solved the problem.
I have given a try for recursive solution. Why don’t you guys give it a try for iterative solution and see if that is more efficient in terms of time and space complexity.
