109. Convert Sorted List to Binary Search Tree[TODO]

Version #2 [TODO]
Count the size once
And take O(n) time to solve


Version #1 Two pointers
Each layer is size 2^depth

for each node, the time to find the slow pointer is O(node length)
Total length is always O(n)
So we need O(nlogn) to solve this problem

53.30 %



public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        //TODO
        return sortedListToBST(head, null);
    }
    private TreeNode sortedListToBST(ListNode head, ListNode tail) {
        if (head == tail) return null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head, slow);
        root.right = sortedListToBST(slow.next, tail);
        return root;
    }
}

108. Convert Sorted Array to Binary Search Tree

二刷 05/2022

Version #1 Recursion

Runtime: 1 ms, faster than 25.32% of Java online submissions for Convert Sorted Array to Binary Search Tree.

Memory Usage: 43.6 MB, less than 53.88% of Java online submissions for Convert Sorted Array to Binary Search Tree.

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public TreeNode sortedArrayToBST(int[] nums) {

        return helper(nums, 0, nums.length - 1);

    }

    

    private TreeNode helper(int[] nums, int start, int end) {

        if (start > end) {

            return null;

        }

        int mid = start + (end - start) / 2;

        TreeNode node = new TreeNode(nums[mid]);

        node.left = helper(nums, start, mid - 1);

        node.right = helper(nums, mid + 1, end);

        return node;

    }

}

Version #2 Iteration with Stack

Runtime: 5 ms, faster than 25.32% of Java online submissions for Convert Sorted Array to Binary Search Tree.

Memory Usage: 43.3 MB, less than 65.50% of Java online submissions for Convert Sorted Array to Binary Search Tree.

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    class NodeInfo {

        int start, end;

        TreeNode node;

        public NodeInfo(TreeNode node, int start, int end) {

            this.start = start;

            this.end = end;

            this.node = node;

        }

    }

    public TreeNode sortedArrayToBST(int[] nums) {

        // Use a stack to do a pre order traversal of the tree

        if (nums == null || nums.length == 0) {

            return null;

        }

        int start = 0, end = nums.length - 1;

        TreeNode root = new TreeNode(nums[(start + end) / 2]);

        NodeInfo rootInfo = new NodeInfo(root, start, end);

        Stack<NodeInfo> stack = new Stack<>();

        stack.push(rootInfo);

        while (!stack.isEmpty()) {

            NodeInfo currInfo = stack.pop();

            int mid = (currInfo.start + currInfo.end) / 2;

            // System.out.printf("start%d, end%d,mid%d -> node %d\n", currInfo.start, currInfo.end, mid, currInfo.node.val);

            NodeInfo right = buildNodeInfo(nums, mid + 1, currInfo.end);

            NodeInfo left = buildNodeInfo(nums, currInfo.start, mid - 1);

            

            if (right != null) {

                currInfo.node.right = right.node;

                stack.push(right);

            }

            if (left != null) {

                currInfo.node.left = left.node;

                stack.push(left);

            }

        }

        return root;

    }

    

    private NodeInfo buildNodeInfo(int[] nums, int start, int end) {

        if (start > end) {

            return null;

        }

        return new NodeInfo(new TreeNode(nums[(start + end) / 2]), start, end);

    }

}

一刷

Version #2 Iteration[TODO]
好像很复杂啊。。。

Version #1 Recursion  13.60 %
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }
    private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if (start > end) return null;
        if (start == end) return new TreeNode(nums[start]);
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, start, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, end);
        return root;
    }
}

106. Construct Binary Tree from Inorder and Postorder Traversal

二刷
Version #2 Iterative

感觉特别特别难, 希望下次做能更理解
91.24 % 
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0
            || postorder == null || postorder.length == 0
            || inorder.length != postorder.length) return null;
        int inPointer = inorder.length - 1;
        int postPointer = postorder.length - 1;
        //                inp
        // inorder = [9,3,15,20,7]
        //             postp
        // postorder = [9,15,7,20,3]
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(postorder[postPointer]);
        stack.push(root);
        postPointer--;
        TreeNode prev = null;
        TreeNode curr = null;
        while (postPointer >= 0) {
            while (!stack.isEmpty() && stack.peek().val == inorder[inPointer]) {
                prev = stack.pop();
                inPointer--;
            }
            // Walk down to the right most node
            curr = new TreeNode(postorder[postPointer--]);
         
            if(prev == null) { // stack won't be null if prev == null
                stack.peek().right = curr;
            } else {
                prev.left = curr;
             
            }
            prev = null;
            stack.push(curr);
        }
        return root;
    }
}



Version #1
Divide and conquer + HashMap Cache
Time O(n)
Space O(n)
 91.21 %
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) throw new IllegalArgumentException();
        Map<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        return buildTreeHelper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1, inMap);
     
    }
    private TreeNode buildTreeHelper(int[] inorder, int[] postorder,
                                     int inStart, int inEnd, int postStart, int postEnd,
                                     Map<Integer, Integer> inMap) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        int curr = postorder[postEnd];
        TreeNode currNode = new TreeNode(curr);
        if (inStart != inEnd) {
            int i = inMap.get(curr);
            currNode.left = buildTreeHelper(inorder, postorder, inStart, i - 1, postStart, postStart + (i - 1 - inStart), inMap);
            currNode.right = buildTreeHelper(inorder, postorder, i + 1, inEnd, postEnd - inEnd + i, postEnd - 1, inMap);
            // inEnd - i - 1 = postEnd - 1 - x
        }
     
        return currNode;
    }
}

Version #2
Iterative

一刷
和105是一样的题
注意PostOrder是
 LEFT -> RIGHT -> ROOT
28.94 %
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null) return null;
        //TODO
        return buildTree(inorder, 0, inorder.length - 1, postorder, postorder.length - 1);
    }
    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postEnd) {
        if (inStart > inEnd || inEnd >= inorder.length) return null;
        int rootVal = postorder[postEnd];
        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) inIndex = i;
        }
        int rightLength = inEnd - inIndex;
        TreeNode root = new TreeNode(rootVal);
        root.right = buildTree(inorder, inIndex + 1, inEnd, postorder, postEnd - 1);
        root.left = buildTree(inorder, inStart, inIndex - 1, postorder, postEnd - 1 - rightLength);
        return root;
    }
}

105. Construct Binary Tree from Preorder and Inorder Traversal

Version #2 Stack Iteration[TODO]

二刷 07/2022

Version #3 Recursion with O(N) time - 可以用hashmap记录value和inorder index的map，这样每次不需要iterate去找到root

Time O(N)

Space O(N)

Runtime: 3 ms, faster than 88.47% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

Memory Usage: 44.4 MB, less than 47.16% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        Map<Integer, Integer> inMap = new HashMap<>();

        // key-value of the node, value-index of that value in the inorder array

        for (int i = 0; i < inorder.length; i++) {

            inMap.put(inorder[i], i);

        }

        return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);

    }

    

    private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {

        if (preStart > preEnd || preStart >= preorder.length) {

            return null;

        }

        TreeNode root = new TreeNode(preorder[preStart]);

        if (preStart == preEnd) {

            return root;

        }

        int inIndex = inMap.get(root.val);

        // [inStart, inIndex - 1] root [inIndex + 1, inEnd]

        // root [preStart + 1, preStart + inIndex - inStart] [preStart + inIndex - inStart + 1, preEnd]

        root.left = buildTreeHelper(preorder, preStart + 1, preStart + inIndex - inStart, inorder, inStart, inIndex - 1, inMap);

        root.right = buildTreeHelper(preorder, preStart + inIndex - inStart + 1, preEnd, inorder, inIndex + 1, inEnd, inMap);

        return root;

    }

}

Version #1 Recursion

写了一个bug就是root.left的preStart parameter应该是preStart + 1因为排除了第一个root的值

另外一个就是要检查preStart是不是出界

Time O(Nh) -> O(N^2) worst

Space O(1)

Runtime: 4 ms, faster than 64.48% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

Memory Usage: 44.6 MB, less than 40.80% of Java online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        // preorder: root -> left -> right

        // inorder: left -> root -> right

        return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);

    }

    

    private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {

        if (preStart > preEnd || preStart >= preorder.length) {

            return null;

        }

        TreeNode root = new TreeNode(preorder[preStart]);

        if (preStart == preEnd) {

            return root;

        }

        int i = 0;

        for (i = inStart; i <= inEnd; i++) {

            if (inorder[i] == root.val) {

                break;

            }

        }

        // preorder preorder[0], pre

        // left part [inStart, i - 1], right part [i + 1, inEnd]

        root.left = buildTreeHelper(preorder, preStart + 1, preStart + (i - inStart), inorder, inStart, i - 1);

        root.right = buildTreeHelper(preorder, preStart + (i + 1 - inStart), preEnd, inorder, i + 1, inEnd);

        return root;

    }

}

一刷
Version #1 Recursion
Preorder的第一个index是root
在inorder里面找到root可以把当前layer parse为left subtree & right subtree
然后到下一层进行recursion construction

难点在于需要的参数
第一个index是必须的 -> preStart
根据preStart之后， 在inorder的给定范围内搜索这个值，所以需要inStart和inEnd
搜索到之后确定的是inIndex
这时候left subtree 和right subtree的length都可以确定了，所以不再需要其他参数

Base case写的比较草率。。。竟然也过了
这里的根据是不要出现死循环或者出界，没有想更多
Space O(1) 没有extra data structure
Time O(nlogn)我猜的 每一层是O(n), 一共大概是logn层


65.22 %

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) return null;
        //TODO
        return buildTree(preorder, 0, inorder, 0, inorder.length - 1);
    }
   
    /*
          inStart      inIndex   inEnd
    inorder  4    1  3     5       2
   
            preStart  leftLength rightLength
    preorder   5       1  4  3        2
         root[5]
   left[4 1 3]   right[2]
   
    */
    private TreeNode buildTree(int[] preorder, int preStart, int[] inorder, int inStart, int inEnd) {
        if (inStart > inEnd || inEnd >= inorder.length) return null;
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) inIndex = i;
        }
        root.left = buildTree(preorder, preStart + 1, inorder, inStart, inIndex - 1);
        root.right = buildTree(preorder, preStart + 1 + (inIndex - inStart), inorder, inIndex + 1, inEnd);
        return root;
    }
}

104. Maximum Depth of Binary Tree

Version #1 Recursion
15.47 %

public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

99. Recover Binary Search Tree

难点是给那个invaliPair赋值
有一种特殊情况是switch两个相邻的值，这样prev和curr会同时发现
所以不能用if else语句
这里的逻辑是每次都把curr更新为invalidPair[1]
而对于invalidPair[0]只赋值一次
这样如果相邻则一次性都赋值，如果不相邻后面的invalidPair[1]也会把之前的覆盖掉


74.90 %
/*
invalid pairs:

    prev curr
          prev  curr
1   [4     3    2]   5
*/


public class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode[] invalidPair = new TreeNode[2];
        recoverTree(root, invalidPair);
        if (invalidPair[0] != null && invalidPair[1] != null) {
           
            int temp = invalidPair[0].val;
            invalidPair[0].val = invalidPair[1].val;
            invalidPair[1].val = temp;
        }
    }
    private TreeNode prev = null;
    private void recoverTree(TreeNode root, TreeNode[] invalidPair) {
        if (root == null) return;
        recoverTree(root.left, invalidPair);
       
        if (prev != null && prev.val >= root.val) {
            if(invalidPair[0] == null) {
                invalidPair[0] = prev;
            }
            invalidPair[1] = root;
        }
        prev = root;
        recoverTree(root.right, invalidPair);
    }
}

95. Unique Binary Search Trees II

Version #2 DP[TODO]

Version #1 Recursion
三刷
91.35 %
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        return dfs(1, n);
    }
   
    private List<TreeNode> dfs(int start, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (start > end) {
            result.add(null);
            return result;
        }
        if (start == end) {
            result.add(new TreeNode(start));
            return result;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = dfs(start, i - 1);
            List<TreeNode> right = dfs(i + 1, end);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode curr = new TreeNode(i);
                    curr.left = l;
                    curr.right = r;
                    result.add(curr);
                }
            }
        }
        return result;
    }
}

二刷
89.35 %
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n <= 0) {
            return new ArrayList<>();
        }
        // given a range, select a root
        return dfs(1, n);
    }
    private List<TreeNode> dfs(int start, int end) {
        if (start > end) {
            return Collections.singletonList(null);
        }
        if (start == end) {
            return Collections.singletonList(new TreeNode(start));
        }
        List<TreeNode> result = new ArrayList<>();
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = dfs(start, i - 1);
            List<TreeNode> right = dfs(i + 1, end);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    result.add(root);
                }
            }
        }
        return result;
    }
}

一刷
 48.52 %
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> result = new ArrayList<>();
        if (n <= 0) return result;
        //TODO
        return generateTrees(1, n);
    }
    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> subResult = new ArrayList<>();
        if (start > end) {
            subResult.add(null);
            return subResult;
        }
        if (start == end) {
            subResult.add(new TreeNode(start));
            return subResult;
        }
        List<TreeNode> left, right;
        for (int mid = start; mid <= end; mid++) {
            left = generateTrees(start, mid - 1);
            right = generateTrees(mid + 1, end);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(mid);
                    root.left = l;
                    root.right = r;
                    subResult.add(root);
                }
            }
        }
        return subResult;
    }
}