Leetcode 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 3 4 5 6 |
1 / \ 2 2 / \ / \ 3 4 4 3 |
But the following [1,2,2,null,3,null,3] is not:
|
1 2 3 4 5 6 |
1 / \ 2 2 \ \ 3 3 |
Note:
Bonus points if you could solve it both recursively and iteratively.
equal(left, right)then we recursively call equal(left.left, right.right) and equal(left.right, right.left).
The method returns false as long as only one of the two nodes is null, or the two nodes contains different values.
Java Implementation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isSymmetric(TreeNode root) { if(root == null) return true; return equal(root.left, root.right); } boolean equal(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if(left == null) return false; if(right == null) return false; if(left.val != right.val) return false; return equal(left.left, right.right) && equal(left.right, right.left); } } |
Iterative Algorithm
We can use level order traverse to solve this problem. We define two queues: curLevel and nextLevel. Initially, the root is inserted into curLevel. Then for each element in curLevel, its children are inserted into the nextLevel with the constraints that the left child comes before the right child.
Before the next round, we check whether the elements in the nextLevel is symmetric. To make this check faster, we use ArrayList as the queue, because it supports fast index based look up.
Different from a standard level order traverse, in which a null child is not inserted into the nextLevel queue. However, to solve this problem, we have to insert a null child into the nextLevel queue. Otherwise, both A = [3, null, null, 3], and B = [null, 3, null, 3] will become [3, 3], which is symmetric. However, B is not symmetric.
So we need to record the null pointer in the nextLevel queue to represent the structure of the tree.
Level order traverse: Java Implementation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isSymmetric(TreeNode root) { if(root == null) return true; return symmetric(root); } boolean symmetric(TreeNode root) { ArrayList<TreeNode> firstLevel = new ArrayList<>(); firstLevel.add(root); boolean lastNevel = false; // No need to check the last level while(!lastNevel && firstLevel != null && !firstLevel.isEmpty()) { ArrayList<TreeNode> nextLevel = new ArrayList<>(); for(TreeNode cur: firstLevel ) { if( cur == null){ // if current node is null, we need to insert two nulls into the queue if (!lastNevel){ nextLevel.add(null); nextLevel.add(null); } continue; } nextLevel.add(cur.left); nextLevel.add(cur.right); lastNevel = true; if(cur.left != null || cur.right != null) lastNevel = false; } firstLevel = null; if(!isListSymmetric(nextLevel) ) return false; firstLevel = nextLevel; } return true; } boolean isListSymmetric(ArrayList<TreeNode> list) { int end = list.size() - 1; int start = 0; TreeNode startNode, endNode; while(start < end) { startNode = list.get(start); endNode = list.get(end); if(startNode == null && endNode == null) { start++; end--; continue; } if(startNode == null) return false; if(endNode == null) return false; if(startNode.val != endNode.val) { return false; } else{ start++; end--; } } return true; } } |
An improved solution
The above implementation may not pass certain kinds to test cases, Here is an improved solution. For each level, there are two queues: leftQ and rightQ.
The leftQ aims to record the left half and the rightQ aims to record the right half of the nodes for the next level, but they are in the contrary direction.
See the following java implementation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
public boolean solve(TreeNode root){ if(root == null) return true; Queue<TreeNode> leftQ = new LinkedList<TreeNode>(); Queue<TreeNode> rightQ = new LinkedList<TreeNode>(); leftQ.add(root.left); // record the left half of the nodes in the next level rightQ.add(root.right); // record the right half of the nodes in the next level TreeNode left, right; while(!leftQ.isEmpty() && !rightQ.isEmpty()){ left = leftQ.poll(); right = rightQ.poll(); if(left == null && right == null) continue; else if(left == null || right == null) return false; if(left.val != right.val){ return false; } else{ //they are in contrary direction //leftQ {left to right direction} //rightQ {right to left direction} leftQ.add(left.left); leftQ.add(left.right); rightQ.add(right.right); rightQ.add(right.left); } } return true; } |
Reference:
https://leetcode.com/problems/symmetric-tree/
http://www.geeksforgeeks.org/symmetric-tree-tree-which-is-mirror-image-of-itself/
http://fisherlei.blogspot.com/2013/01/leetcode-symmetric-tree.html
http://www.programcreek.com/2014/03/leetcode-symmetric-tree-java/
