binary tree - 20200201

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        
        return (left>right? left:right) +1;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null){
            return new ArrayList<>();
        }
        
        List<String> totalPath = new ArrayList<>();
        if(root.left == null && root.right == null){
            totalPath.add(root.val + "");
            return totalPath;
        }
        
        List<String> leftPaths = binaryTreePaths(root.left);
        List<String> rightPaths = binaryTreePaths(root.right);
        
        for(String path:leftPaths){
            totalPath.add(root.val + "->"+path);
        }
        
        for(String path:rightPaths){
            totalPath.add(root.val + "->" + path);
        }
        
        return totalPath;
        
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class BalancedHelper{
    public boolean isBalanced;
    public int depth;
    public BalancedHelper(boolean isBalanced, int depth){
        this.depth = depth;
        this.isBalanced = isBalanced;
    }
}


class Solution {
    public boolean isBalanced(TreeNode root) {
        return Helper(root).isBalanced;
    }
    
    public BalancedHelper Helper(TreeNode root){
        if(root == null){
            return new BalancedHelper(true, 0);
        }
        
        BalancedHelper leftBalance = Helper(root.left);
        BalancedHelper rightBalance = Helper(root.right);
        
        if(!leftBalance.isBalanced || !rightBalance.isBalanced){
            return new BalancedHelper(false, -1);
        }
        
        if(Math.abs(leftBalance.depth - rightBalance.depth) > 1){
            return new BalancedHelper(false, -1);
        }
        
        return new BalancedHelper(true, 1+ Math.max(leftBalance.depth, rightBalance.depth));
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class LCAHelper{
    public boolean isExistA;
    public boolean isExistB;
    public TreeNode node;
    public LCAHelper(boolean isExistA, boolean isExistB, TreeNode node){
        this.isExistA = isExistA;
        this.isExistB = isExistB;
        this.node = node;
    }
}
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        LCAHelper rootHelper = Helper(root,p,q);
        if(rootHelper.isExistA && rootHelper.isExistB){
            return rootHelper.node;
        }
        
        return null;
    }
    
    public LCAHelper Helper(TreeNode root, TreeNode A, TreeNode B){
        if(root == null){
            return new LCAHelper(false, false, null);
        }
        
        LCAHelper leftHelper = Helper(root.left,A,B);
        LCAHelper rightHelper = Helper(root.right,A,B);
        
        boolean isExistA = (root==A)||leftHelper.isExistA || rightHelper.isExistA;
        boolean isExistB = (root == B)||leftHelper.isExistB || rightHelper.isExistB;
        
        if(root == A || root == B){
            return new LCAHelper(isExistA, isExistB, root);
        }
        
        if(leftHelper.node != null && rightHelper.node != null){
            return new LCAHelper(isExistA, isExistB, root);
        }
        
        if(leftHelper.node != null){
            return new LCAHelper(isExistA, isExistB, leftHelper.node);
        }
        
        if(rightHelper.node != null){
            return new LCAHelper(isExistA, isExistB, rightHelper.node);
        }
        
        return new LCAHelper(isExistA, isExistB, null);
    }

}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTHelper {
    public boolean isValidBST;
    public int max;
    public int min;
    public BSTHelper(boolean isValidBST, int min, int max){
        this.isValidBST = isValidBST;
        this.min = min;
        this.max = max;
    }
}
class Solution {
    public boolean isValidBST(TreeNode root) {
        return Helper(root).isValidBST;
    }
    
    public BSTHelper Helper(TreeNode root){
        if(root == null){
            return new BSTHelper(true, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }
        
        BSTHelper leftHelper = Helper(root.left);
        BSTHelper rightHelper = Helper(root.right);
        
        if(!leftHelper.isValidBST || !rightHelper.isValidBST){
            return new BSTHelper(false, 0 , 0);
        }
        
        if(root.left != null && leftHelper.max >= root.val){
            return new BSTHelper(false, 0 ,0);
        }
        
        if(root.right != null && rightHelper.min <= root.val){
            return new BSTHelper(false, 0 ,0);
        }
        
        return new BSTHelper(true, Math.min(leftHelper.min, root.val), Math.max(rightHelper.max, root.val));
        
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        Helper(root);
    }
    
    public TreeNode Helper(TreeNode root){
        if(root == null){
            return null;
        }
        
        TreeNode leftLast = Helper(root.left);
        TreeNode rightLast = Helper(root.right);
        
        if(leftLast != null){
            leftLast.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        
        if(rightLast != null){
            return rightLast;
        }
        
        if(leftLast != null){
            return leftLast;
        }
        
        return root;
    }
}