Problem
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.
Solution 1
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if (!root) return true;
return helper(root.left, root.right);
};
var helper = function (p, q) {
if ((!p && q) || (p && !q) || (p && q && p.val !== q.val)) return false;
if (p && q) return helper(p.left, q.right) && helper(p.right, q.left);
return true;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).
Solution 2
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if (!root) return true;
var p = [root.left];
var q = [root.right];
var ll = null;
var rr = null;
while (p.length && q.length) {
ll = p.pop();
rr = q.pop();
if (!ll && !rr) continue;
if (!ll || !rr) return false;
if (ll.val !== rr.val) return false;
p.push(ll.left);
p.push(ll.right);
q.push(rr.right);
q.push(rr.left);
}
return true;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).