Java 1ms O(n) bottom-up solution without using arrays. (recursion)


  • 0

    Key points:

    1. Using a global variable to store the max count, so don't need the count the total node after finding the BST subtree. 2. To make each recursion has the starting condition of min < root.val < max, the function checks the child node's value first before calling the next recursion. In addition, the null nodes can be avoided.

      public class Solution {
      int res = 0; // store the max count of BST nodes
      int helper(TreeNode root, long min, long max) {
      if ( root == null ) return 0;
      long value = (long) root.val;
      int left = 0; // store left size's BST nodes. If -1, not a BST root.
      int right = 0; // store right size's BST nodes. If -1, not a BST root.
      boolean out_of_range = false;
      // if one of the child nodes is out of the range,
      // than the previous node is not a root of BST
      if ( root.left != null ) {
      long lv = (long) root.left.val;
      if ( lv > value ) {
      // current node is not a root of BST, reset both ends
      helper(root.left, Long.MIN_VALUE, Long.MAX_VALUE);
      left = -1;
      out_of_range = true;
      } else {
      if ( lv < min) {
      // previous node is not a root of BST, reset min value
      left = helper(root.left, Long.MIN_VALUE, value);
      out_of_range = true;
      } else {
      // previous node is possible to be a root of BST
      left = helper(root.left, min, value);
      }
      }
      }
      if ( root.right != null ) {
      long rv = (long) root.right.val;
      if ( rv < value ) {
      // current node is not a root of BST, reset both ends
      helper(root.right, Long.MIN_VALUE, Long.MAX_VALUE);
      right = -1;
      out_of_range = true;
      } else {
      if ( rv > max) {
      // previous node is not a root of BST, reset max value
      right = helper(root.right, value, Long.MAX_VALUE);
      out_of_range = true;
      } else {
      // previous node is possible to be a root of BST
      right = helper(root.right, value, max);
      }
      }
      }
      if ( ( left >= 0 ) && ( right >= 0 ) ) {
      // both child nodes are roots of BST
      // and left.val < root.val < right.val
      int ret = left+right+1; // count the total BST nodes
      res = Math.max(res, ret); // record the maximun nodes
      if ( ! out_of_range ) {
      // pass the count back if the privious node is still in the range
      return ret;
      }
      }
      return -1;
      }
      public int largestBSTSubtree(TreeNode root) {
      helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
      return res;
      }
      }


Log in to reply
 

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