I am not able to know where I am commiting a mistake


  • 2
    D

    I am doing it by comparing the inorder traversal list with its reverse. If they are equal, then the tree is symmetric otherwise not.

    public class Solution {
        public boolean isSymmetric(TreeNode root) {
            ArrayList<Character> list = inorderTraversal(root), list2;
            list2 = (ArrayList<Character>) list.clone();
            Collections.reverse(list);
            if(list2.equals(list))
            {
                return true;
            }
            return false;
        }
        
        public ArrayList<Character> inorderTraversal(TreeNode root) {
            ArrayList<Character> list = new ArrayList<Character> ();
            if(root == null)
            {
                list.add('#');
                return list;
            }
            list.addAll(inorderTraversal(root.left));
            list.add(Integer.toString(root.val).toCharArray()[0]);
            list.addAll(inorderTraversal(root.right));
            return list;
            
        }
    }
    

    But, The OJ says that my solutions gives true for the input : {1,2,3,3,#,2,#}
    I am not able to see how!!


  • 0
    S

    Please draw the tree on paper, and its inorder string. You will find out the problem.


  • 0
    H

    Shangrila's answer is the key, and what I want to share with you is that, you should use some test cases to analysis your algorithm, and more importantly, use these test cases to test your code before you submit.


  • 0
    X

    When you goes to leaf node, it will produce 2 '#'. That's where the problem lies.


  • 1
    N

    In the test case {1,2,3,3,#,2,#}, your result list is {#3#2#1#2#3#}, which is symmetric. But obviously the second level {2, 3} is not symmetric. In order travel cannot work for symmetric judgement. I think BFS should be used and test symmetry level by level. The following is my code.

    bool isLeaf(TreeNode* node)
    {
        if(node)
            return (node->left==NULL && node->right==NULL);
        else
            return false;
    }
    bool isMirror(TreeNode* node1, TreeNode* node2)
    {
        if(node1==NULL && node2==NULL)
            return true;
        if(!(node1 && node2))   //one null
            return false;
        if(node1->val!=node2->val)
            return false;
        return (isMirror(node1->left, node2->right) && isMirror(node1->right, node2->left));
    }
    
    //recursive solution
    bool isSymmetric(TreeNode *root) {
        if(root==NULL) return true;
        if(isLeaf(root)) return true;
        return isMirror(root->left, root->right);
    }

  • 0
    X

    Not necessary the same with same inorder traversal.


  • 0
    P

    I don't think you need the check leaf function


  • 0
    F
          1
        /    \
       2     3
      /      /
     3     2    
    

    and

          1
        /    \
       2     2
      /        \
     3         3
    

    their inorder traversal list is all the same: {#3#2#1#2#3#}.

    It means that a asymmetric tree may work out a symmetric list.So your algorithm has a bug.Maybe you need two different traversal to Identify the unique tree.


Log in to reply
 

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