Maximum Binary Tree


  • 0

    Click here to see the full article post


  • 0
    S

    Can you flesh our the Time complexity using recurrence relations? It is stated that the average case is nlogn, but don't you mean the best (aka balanced tree) case?


  • 0
    J

    @sean46: https://stackoverflow.com/questions/10324830/how-to-get-onlogn-from-tn-2tn-2-on

    Are you good with the relation being approx: T(n) = O(n) + 2T(n/2)? You can then look at the above link and see that it is nlogn.

    I guess it is more like T(n) = O(n) + T(m) + T(n-m)


  • 0
    R

    O(n) complexity and O(n) space JAVA Solution

    /**

    • Definition for a binary tree node.

    • public class TreeNode {

    • int val;
      
    • TreeNode left;
      
    • TreeNode right;
      
    • TreeNode(int x) { val = x; }
      
    • }
      */
      class Solution {
      TreeNode root = null;
      HashMap<TreeNode,TreeNode> parentMap = new HashMap<>();
      public TreeNode constructMaximumBinaryTree(int[] nums) {
      if(nums.length==0) return null;

       TreeNode current = new TreeNode(nums[0]);
       root = current;
       for(int idx=1; idx<nums.length; idx++) {
           TreeNode newNode = new TreeNode(nums[idx]);
           if(newNode.val<current.val) {
               //next element value less than current. next element goes to the right of current
               current.right=newNode;
               parentMap.put(newNode, current);
               current=newNode;
           } else {
               //find its correct position
               insertNode(current, newNode);
               current=newNode;
           }
       }
       return root;
      

      }
      public void insertNode(TreeNode current, TreeNode newNode) {
      //iterate till I get parent greater than new element or new element is new root.
      while(parentMap.get(current)!=null && parentMap.get(current).val<newNode.val) {
      current = parentMap.get(current);
      }
      if(parentMap.get(current)==null) {
      //if new element is root
      root = newNode;
      newNode.left = current;
      parentMap.put(current, newNode);
      } else {
      //Noew parent is greater than new element. It will always come from right subtree. Thus make the new element right child of parent and current right subtree the left child(the whole left sub tree came before new element) of new element.
      TreeNode parent = parentMap.get(current);
      TreeNode temp = parent.right;
      parent.right=newNode;
      newNode.left = temp;
      parentMap.put(newNode, parent);
      parentMap.put(current, newNode);
      }
      }
      }


  • 0
    R

    O(n) complexity and O(n) space JAVA Solution

    class Solution {
    TreeNode root = null;
    HashMap<TreeNode,TreeNode> parentMap = new HashMap<>();
    public TreeNode constructMaximumBinaryTree(int[] nums) {
    if(nums.length==0) return null;

        TreeNode current = new TreeNode(nums[0]);
        root = current;
        for(int idx=1; idx<nums.length; idx++) {
            TreeNode newNode = new TreeNode(nums[idx]);
            if(newNode.val<current.val) {
                //next element value less than current. next element goes to the right of current
                current.right=newNode;
                parentMap.put(newNode, current);
                current=newNode;
            } else {
                //find its correct position
                insertNode(current, newNode);
                current=newNode;
            }
        }
        return root;
    }
    public void insertNode(TreeNode current, TreeNode newNode) {
        //iterate till I get parent greater than new element or new element is new root.
        while(parentMap.get(current)!=null && parentMap.get(current).val<newNode.val) {
            current = parentMap.get(current);
        }
        if(parentMap.get(current)==null) {
            //if new element is root
            root = newNode;
            newNode.left = current;
            parentMap.put(current, newNode);
        } else {
            //Noew parent is greater than new element. It will always come from right subtree. Thus make the new element right child of     parent and current right subtree the left child(the whole left sub tree came before new element) of new element. 
            TreeNode parent = parentMap.get(current);
            TreeNode temp = parent.right;
            parent.right=newNode;
            newNode.left = temp;
            parentMap.put(newNode, parent);
            parentMap.put(current, newNode);
        }
    }
    

    }


  • 0
    X

    iterative way to o(n) time complexity and o(n) space complexity.
    Use deque because need to use the front element of stack at the last step.

    This solution is inspired by @votrubac
    https://discuss.leetcode.com/topic/98454/c-9-lines-o-n-log-n-map

    1. traverse the array once and create the node one by one. and use stack to store a decreasing sequence.
      2, each step when we create a new curNode. compare to the peek of stack,
      2.a . keep popping the stack while the peek < curNode, and set the last popping node to be curNode.left. Because the last one is the largest number among curNode's left children. => curNode.left = last pop node
      2.b . after popping up all (node.val < curNode), the peek is curNode's root => peek.right = curNode
      3 return the first element of stack.

    Because of the last step, I use Deque to do all operations.

    class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
    if (nums == null || nums.length == 0) {
    return null;
    }

        Deque<TreeNode> dq = new LinkedList();
        
        for (int i = 0; i < nums.length; i++) {
            TreeNode curNode = new TreeNode(nums[i]);
            
            while (!dq.isEmpty() && dq.peek().val < nums[i]) {
                curNode.left = dq.peek();
                dq.pop();
            }
            
            if (!dq.isEmpty()) {
                dq.peek().right = curNode;
               
            }
            dq.push(curNode);
        }
        
        return dq.peekLast();
    }
    

    }


  • 0

    /**

    • Definition for a binary tree node.

    • public class TreeNode {

    • int val;
      
    • TreeNode left;
      
    • TreeNode right;
      
    • TreeNode(int x) { val = x; }
      
    • }
      */
      class Solution {
      public TreeNode constructMaximumBinaryTree(int[] nums) {

       int max=0;
       int maxIndex=0;
       
       for(int i=0;i<nums.length;i++){
          if(nums[i]>max){
             max=nums[i];
             maxIndex=i;
          }
       }
        TreeNode root=new TreeNode(max);
      

      if(maxIndex!=0 && nums.length!=0){
      int leftArray[] = Arrays.copyOfRange(nums, 0, maxIndex);
      root.left=constructMaximumBinaryTree(leftArray);
      }
      if(maxIndex!=nums.length-1 && nums.length!=0) {
      int rightArray[] = Arrays.copyOfRange(nums, maxIndex+1, nums.length);
      root.right=constructMaximumBinaryTree(rightArray);
      }
      return root;
      }
      }


  • 0
    T

    I think a simple O(nlogn) solution should be included as one of the accepted solutions: see the code: https://repl.it/@toravir/QuickDizzyPaintedladybutterfly


Log in to reply
 

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