Why does this recursive solution causes time limited exceeded issuse


  • 0
    H

    Why does this recursive solution causes time limited exceeded issuse

    public class Solution {
        public void flatten(TreeNode root) {
            assign(root);
        }
        
        public TreeNode assign(TreeNode node){
            if(node == null){
                return null;
            }
            // find out the last element of node's left sub tree in pre order;
            TreeNode leftUnAssignNode = assign(node.left);
            // find out the last element of node's right sub tree in pre order;
            TreeNode rightUnAssignNode = assign(node.right);
            if(leftUnAssignNode == null && rightUnAssignNode == null){
                return node;
            }else if(leftUnAssignNode == null && rightUnAssignNode != null){
                return rightUnAssignNode;
            }else if(leftUnAssignNode != null && rightUnAssignNode == null){
                node.right = node.left;
                node.left = null;
                return leftUnAssignNode;
            }else{
                leftUnAssignNode.right = node.right;
                return rightUnAssignNode;
            }
        }
    }

  • 0
    H

    The right answer

    public class Solution {
        public void flatten(TreeNode root) {
            assign(root);
        }
        
        public TreeNode assign(TreeNode node){
            if(node == null){
                return null;
            }
            // find out the last element of node's left sub tree in pre order;
            TreeNode leftUnAssignNode = assign(node.left);
            
            // find out the last element of node's right sub tree in pre order;
            TreeNode rightUnAssignNode = assign(node.right);
            if(leftUnAssignNode == null && rightUnAssignNode == null){
                return node;
            }else if(leftUnAssignNode == null && rightUnAssignNode != null){
                return rightUnAssignNode;
            }else if(leftUnAssignNode != null && rightUnAssignNode == null){
                node.right = node.left;
                node.left = null;
                return leftUnAssignNode;
            }else{
                leftUnAssignNode.right = node.right;
                node.right = node.left;
                node.left = null;
                return rightUnAssignNode;
            }
        }
    }

Log in to reply
 

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