Preorder traversal O(n) got a TLE??


  • 1
    Y

    My solution is just a variant of preorder traversal. It just iterate over the every node, so the complexity is O(n), but I still got a TLE. Any suggestions?

    // Keep track of previously visited node
    private TreeNode prev = null;
    
    /*
     * Recur version
     */
    public void flatten(TreeNode root) {
        TreeNode dummy = new TreeNode(0);
        dummy.right = root;
        prev = dummy;
        flattenHelper(root);
    }
    
    public void flattenHelper(TreeNode root){
        if (root == null) return;
        prev.right = root;
        prev = root;
        // after invoke flattenHelper on root.left, root.right will revised
        // so record this value
        TreeNode rootRight = root.right;
        flattenHelper(root.left);
        flattenHelper(rootRight);
    }

  • 3
    R

    public void flattenHelper(TreeNode root)

    {

    if (root == null) return;
    
    prev.right = root;
    
    prev.left=null;    **//add this line**
    
    //0 minutes ago	Accepted	 440 ms	java
    //I benlai suppose it shuold be wrong answer without that line, but TLE make me feel a little kendie
    prev = root;
    
    // after invoke flattenHelper on root.left, root.right will revised
    // so record this value
    TreeNode rootRight = root.right;
    flattenHelper(root.left);  //old big,here yinggai is not flatternRecur,I think you write wrong in your question
    flattenHelper(rootRight); //
    

    }


  • 0
    S

    Hey @runny. Thanks for your sharing. Your post is good, but with bad code format. Try to select all code then click {} button to correct it.


  • 0
    Y

    Hi @runny, good answer. Without prev.left=null;, it should be wrong answer, I guess the judge just check node.right, not the whole structure.


  • 0
    S

    It does check the whole data structure. You should make sure the left children are assigned to NULL


  • 0
    D

    yes, I also encounter this problem without assigning the left children to null, after I do that , it is accepted, thanks for all


Log in to reply
 

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