[symmetric tree] why inorder traversal doesn't work?


  • 0
    Y

    My solution for symmetric tree is:

    1. Inorder traverse the binary tree, so for the below tree, I get '3241423'

          1
         /  \
        2    2
       /\    /\
      3 4    4 3
      

    Then simply check if the this string equals to its reverse (i.e., palindrome)

    Below is my python code,

    class Solution:
        x=''
        # @param root, a tree node
        # @return a boolean
        def isSymmetric(self, root):
            if root is None:
                return True
            self.inorder(root)
            return self.x == self.x[::-1]
            
        def inorder(self, node):
            if node is None:
                return
            self.inorder(node.left)
            self.x += str(node.val)
            self.inorder(node.right)
    

    which is however rejected for wrong answer: {1,2} outputs True.

    Why?

    p.s. When I tried to debug, I don't really know how LeetCode builds the tree in the first place (i.e., the input parameter root). Can someone also suggest how to construct the input root?


  • 5
    K

    I think in-order traversal is not the problem itself. A simple serialization doesn't capture the structure of the tree which is important in determining symmetry. For instance the following 2 trees in your solution would be serialized into the same string but they are not the same tree and have different symmetry.

            1
          /
        2
      /
    1
    
    
        2
      /   \
    1       1
    

    I haven't verified this but if you use place holder for empty node and always output a string that represents a "full" tree it might work. It might be harder than it seems.

    12#1###
    
    121
    

    Anyway this method won't be efficient as it has to walk the whole tree and does a huge reverse and then string comparison. Both recursive and iterative solutions exist with early returning.

    As for the tree construction, see the commented out section above the "class Solution" definition. The simple example can be done like this:

    r = TreeNode(1)
    r.right = TreeNode(2)

  • 1
    L

    Comparing the output is palindrome cannot solve this problem.

    Just imagine that, any tree with all nodes having the same value would be considered to be symmetric, by the above solution, which is wrong.


  • 0
    Y

    This is a good and simple counter example.


  • 0
    S

    I got AC using in-order traversal. But I compared the node's layer (depth) in addition to the node's value when I tried to compare the output.

    class Solution:
        # @param root, a tree node
        # @return a boolean
        def isSymmetric(self, root):
            self.trav = []
        	self.in_Order_Trav(root, 0)
        	length = len(self.trav)
    
        	for i in range(length/2):
                if self.trav[i].val != self.trav[length-1-i].val or self.trav[i].layer != self.trav[length-1-i].layer:
                    return False
    
            return True
    
        
        def in_Order_Trav(self, root, layer):
    
            if root!=None:          
                self.in_Order_Trav(root.left,layer+1)
                self.trav.append(MyNode(root.val,layer))
                self.in_Order_Trav(root.right,layer+1)  
    
    class MyNode:
        def __init__(self, val, layer):
            self.layer = layer
            self.val = val

Log in to reply
 

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