# Recursive and non-recursive solutions in Java

• Recursive--400ms:

``````public boolean isSymmetric(TreeNode root) {
return root==null || isSymmetricHelp(root.left, root.right);
}

private boolean isSymmetricHelp(TreeNode left, TreeNode right){
if(left==null || right==null)
return left==right;
if(left.val!=right.val)
return false;
return isSymmetricHelp(left.left, right.right) && isSymmetricHelp(left.right, right.left);
}
``````

Non-recursive(use Stack)--460ms:

``````public boolean isSymmetric(TreeNode root) {
if(root==null)  return true;

Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode left, right;
if(root.left!=null){
if(root.right==null) return false;
stack.push(root.left);
stack.push(root.right);
}
else if(root.right!=null){
return false;
}

while(!stack.empty()){
if(stack.size()%2!=0)   return false;
right = stack.pop();
left = stack.pop();
if(right.val!=left.val) return false;

if(left.left!=null){
if(right.right==null)   return false;
stack.push(left.left);
stack.push(right.right);
}
else if(right.right!=null){
return false;
}

if(left.right!=null){
if(right.left==null)   return false;
stack.push(left.right);
stack.push(right.left);
}
else if(right.left!=null){
return false;
}
}

return true;
}``````

• Nice solution. Thanks for sharing.

• That really helps!

• ``````   if(left==null || right==null)
return left==right;
``````

nice one!

• Agree! Agree! Agree!

• My recursion solution java : 243 ms

``````public boolean isSymmetric(TreeNode root) {
if (root ==null)
return true;
return isSymmetricSubTree(root.left, root.right);
}

public boolean isSymmetricSubTree(TreeNode left,  TreeNode right){
if(left ==null && right ==null) return true;
if(left==null || right ==null) return false;
if(left.val == right.val ) {
return isSymmetricSubTree(left.left, right.right) && isSymmetricSubTree(left.right, right.left);
}else
return false;
}``````

• This post is deleted!

• This post is deleted!

• Smart solution, thanks a lot!

• I don't think this line can pass any code review in any company

• How did you find out the execution time?

• why ? I think it is a good one

• ``````class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root)   return true;
return help(root->left, root->right);
}
bool help(TreeNode* left, TreeNode* right){
if(left==NULL && right==NULL)   return true;
if(left==NULL || right==NULL)   return false;
if(left->val!=right->val)    return false;
else{
/***   the key point is the make sure the sub-tree pair relationship  ***/
return help(left->left, right->right) && help(left->right, right->left);
}
}
};``````

• Thanks for sharing, very easy to understand!

• Same code for Iterative, but just reducing the size :)

``````public boolean isSymmetric(TreeNode root) {
if(root==null)  return true;

Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode left, right;
if(!process(root.left, root.right, stack)) return false;

while(!stack.empty()){
if(stack.size()%2!=0)   return false;
right = stack.pop();
left = stack.pop();
if(right.val!=left.val) return false;
if(!process(left.left, right.right, stack)) return false;
if(!process(left.right, right.left, stack)) return false;
}
return true;
}

public boolean process(TreeNode a, TreeNode b, Stack<TreeNode> s) {
if(a != null) {
if(b == null) return false;
s.push(a);
s.push(b);
}else if(b != null) return false;
return true;
}``````

• nice.thank you.why my commit is 1ms.

• just code clearly.nothing

• what's the time complexity for recursive solution? I think the average is O(logN) while the worst case is O(N). correct me if i am wrong.

• It is o(n) since it has to traverse whole tree.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.