Why in order traversal serialization including NULL nodes doesn't work?


  • 0
    W

    Here is my code. It first store the in order traversal including NULL nodes in to a vector and check the symmetry of the vector. OJ keeps telling me:
    Input: {1,2,3,3,#,2,#}
    Output: true
    Expected: false

    My serialized vector would be {3, 2, #, 1, 2, 3, #} and the symmetry check on the vector would be false. Could anyone point out what is wrong in my code?

    bool isSymmetric(TreeNode *root) {

        vector<TreeNode *> nodes;
        InOrderTraversal(root, nodes);
        int size = nodes.size();
        for (int i = 0; i < size; i++) {
            TreeNode *node1 = nodes[i];
            TreeNode *node2 = nodes[size - 1 - i];
            if (node1 && node2) {
                if (node1->val != node2->val)
                    return false;
            } else if (node1 || node2) {
                return false;
            }
        }
        
        return true;
    }
    
    void InOrderTraversal(TreeNode *node, vector<TreeNode *> &nodes)
    {
        if (node) {
            InOrderTraversal(node->left, nodes);
        }
        nodes.push_back(node);
        if (node) {
            InOrderTraversal(node->right, nodes);
        }
    }

  • 2
    L

    are you sure your serialized vector (after InOrderTravesal() ) would be {3, 2, #,1,2,3,#} ?
    you didn't deal with the case when the node is "#" in the travesal function..


  • 0
    W

    The traversal function always does "nodes.push_back(node);", so the "#" (the null pointer) is added to the vector.


  • 0
    L

    your process of the null case is wrong;
    your serialized vector will be {#, 3,#,2,#,1, #,2,#,3,#}; and its symmetric will be true.
    need modify your traversal function..


  • 0
    L
    This post is deleted!

  • 0
    W

    good catch! thanks for pointing that out


Log in to reply
 

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