MrainW's Home

class Solution {
    int sum = 0;
    public int sumNumbers(TreeNode root) {
        if (root == null)
            return 0;
        dfs(root, 0);
        return sum;
    }
    private void dfs(TreeNode root, int num){
        num = num * 10 + root.val;
        if (root.left == null && root.right == null){
            sum += num;
            return;
        }
        if (root.left != null) dfs(root.left, num);
        if (root.right != null) dfs(root.right, num);
    }
}

class Solution {
    int maxvalue = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxvalue;
    }
    public int dfs(TreeNode node){
        if (node == null) return 0;
        int left = dfs(node.left);
        int right = dfs(node.right);
        left = left < 0 ? 0 : left;
        right = right < 0 ? 0 : right;
        maxvalue = Math.max(maxvalue, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}

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

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }
}

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;
        if(key < root.val) root.left = deleteNode(root.left, key);
        else if(key > root.val) root.right = deleteNode(root.right, key);
        else if(root.left == null) return root.right;
        else if(root.right == null) return root.left;
        else{
            root.val = findMin(root.right);
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }
    private int findMin(TreeNode node){
        while(node.left != null) node = node.left;
        return node.val;
    }
}

class Solution {
    Node pre = null, head = null;
    public Node treeToDoublyList(Node root) {
        if (root == null) return root;
        inorderTraversal(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    private void inorderTraversal(Node root){
        if(root == null) return;
        inorderTraversal(root.left); //left
        if(head == null) head = root;
        if(pre != null) pre.right = root; //root
        root.left = pre;
        pre = root;
        inorderTraversal(root.right); //right
    }
}

class Solution {
    int[] inorder;
    int[] postorder;
    int N;
    Map<Integer, Integer> inMap = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.inorder = inorder;
        this.postorder = postorder;
        N = inorder.length;
        for (int i = 0; i < N; i++) inMap.put(inorder[i], i);
        return helper(0, N - 1, 0, N - 1);
    }
    public TreeNode helper(int inStart, int inEnd, int postStart, int postEnd){
        if (inStart > inEnd) return null;
        TreeNode root = new TreeNode(postorder[postEnd]);
        int inIndex = inMap.get(root.val);
        int rightTreeSize = inEnd - inIndex;
        root.left = helper(inStart, inIndex - 1, postStart, postEnd - rightTreeSize -1);
        root.right = helper(inIndex + 1, inEnd, postEnd - rightTreeSize, postEnd -1);
        return root;
    }
}

class Solution {
    int[] preorder;
    int[] inorder;
    int preOrderIndex;
    Map<Integer, Integer> treeMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        this.preOrderIndex = 0;
        int N = preorder.length;
        for (int i = 0; i < N; i++) treeMap.put(inorder[i], i);
        return helperbulid(0, N-1);
    }
    public TreeNode helperbulid(int instart, int inend){
        if(instart > inend) return null;
        TreeNode root = new TreeNode(preorder[preOrderIndex++]);
        int index = treeMap.get(root.val);
        root.left = helperbulid(instart, index - 1);
        root.right = helperbulid(index + 1, inend);
        return root;
    }
}

class Solution {
    int index, N;
    int[] preorder;
    public TreeNode helper(int lower, int upper){
        if (index == N) return null;
        int val = preorder[index];
        if (val < lower || val > upper) return null;
        index ++;
        TreeNode root = new TreeNode(val);
        root.left = helper(lower, val);
        root.right = helper(val, upper);
        return root;
    }    
    public TreeNode bstFromPreorder(int[] preorder) {
        this.preorder = preorder;
        N = preorder.length;
        return helper(Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
}

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        String res = String.valueOf(root.val);
        if (root.left != null) res += "," + serialize(root.left);
        if (root.right != null) res += "," + serialize(root.right);
        return res;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        Queue<String> q = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserialize(q, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    public TreeNode deserialize(Queue<String> q, int lower, int upper){
        if (q.isEmpty()) return null;
        String s = q.peek();
        int val = Integer.parseInt(s);
        if (val < lower || val > upper) return null;
        q.poll();
        TreeNode root = new TreeNode(val);
        root.left = deserialize(q, lower, val);
        root.right = deserialize(q, val, upper);
        return root;
    }
}