Java: top down recursive solution with O(N) time and O(1) space


  • 1
    T

    This solution uses top down recursive approach to build the tree.

    Each '(' represents traversing down and ')' represents traversing up.

    We are expecting the first character s.charAt(c.idx) when entering the buildTree() function to be a number (could be positive or negative).

    Then if we see '(' we would want to traverse down and connect the left pointer with the result.

    If we see '(' again we know that's for right sub tree so we recursively call the buildTree() function.

    Remember to increment the idx before building left subtree or right subtree, and increment again after returning. If we increment the index before returning the index might be out of bound.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
      public TreeNode str2tree(String s) {
        return buildTree(s, new Count(0));
      }
    
      private TreeNode buildTree(String s, Count c) {
        if (s == null || c.idx < 0 || c.idx >= s.length()) {
          return null;
        }
    
        int start = c.idx;
        int end = start;
        // get the value for current node
        if (s.charAt(c.idx) == '-') {
          c.idx++;
        }
    
        while(c.idx < s.length() && s.charAt(c.idx) >= '0' && s.charAt(c.idx) <= '9') {
          c.idx++;
        }
    
        end = c.idx;
        
        if (start == end) {
            return null;
        }
          
        TreeNode cur = new TreeNode(Integer.parseInt(s.substring(start, end)));
    
        if (c.idx < s.length() && s.charAt(c.idx) == '(') {
          c.idx++;
          cur.left = buildTree(s, c);
          // ')'
          c.idx++;
        }
    
        if (c.idx < s.length() && s.charAt(c.idx) == '(') {
          c.idx++;
          cur.right = buildTree(s, c);
          c.idx++;
        }
    
        return cur;
      }
    
      private class Count {
        int idx;
        public Count (int _idx) {
          this.idx = _idx;
        }
      }
    }
    

Log in to reply
 

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