101. Symmetric Tree
Last updated
Was this helpful?
Last updated
Was this helpful?
Given a binary tree, check whether it is a mirror of itself (i.e, symmetric around its center).
YouTube
Input: [1, 2, 2, 3, 4, 4, 3]
Output: true
Input: [1, 2, 2, null, 3, null, 3]
Output: false
// 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;
}
}/**
* Time complexity : O(n). Because we traverse the entire input tree once, the
* total run time is O(n), where n is the total number of nodes in the tree.
* Space complexity : The number of recursive calls is bound by the height of
* the tree. In the worst case, the tree is linear and the height is in O(n).
* Therefore, space complexity due to recursive calls on the stack is O(n)
* in the worst case.
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode node1, TreeNode node2) {
if(node1 == null && node2 == null) return true;
if(node1 == null || node2 == null) return false;
if(node1.val != node2.val) return false;
return isMirror(node1.left, node2.right) &&
isMirror(node1.right, node2.left);
}
}/**
* Time complexity : O(n). Because we traverse the entire input tree once, the
* total run time is O(n), where n is the total number of nodes in the tree.
* Space complexity : There is additional space required for the search queue.
* In the worst case, we have to insert O(n) nodes in the queue. Therefore,
* space complexity is O(n).
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
Queue<TreeNode> queue = new LinkedList();
queue.add(root);
queue.add(root);
while(!queue.isEmpty()) {
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
if(node1 == null && node2 == null) continue;
if(node1 == null || node2 == null) return false;
if(node1.val != node2.val) return false;
queue.add(node1.left);
queue.add(node2.right);
queue.add(node1.right);
queue.add(node2.left);
}
return true;
}
}