美文网首页
isValidBST & Balanced binary

isValidBST & Balanced binary

作者: 程序猪小羊 | 来源:发表于2018-06-19 14:03 被阅读33次

    isValidBST

    public boolean isValidBST(TreeNode root) {
    return valid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean valid(TreeNode root, int low, int high) {
    if (root ==null) return true;
    return root.val > low && root.val < high
    && valid(root.left.val, low, root.val) && valid(root,right, root.val, high);
    }

    // Correction:

    1. the corner case:
      if root == null
    2. the first param in "valid" should be TreeNode rather than the value

    // isValidBST

    public boolean isValidBST(TreeNode root) {
    return valid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean valid(TreeNode root, int low, int high) {
    if (root ==null) return true;
    return root.val > low && root.val < high
    && valid(root.left, low, root.val)
    && valid(root,right, root.val, high);
    }

    // When the TreeNode contain the infinite, above code won't work;
    // so we replace the MAX and MIN with null

    private boolean valid(TreeNode root, int low, int high) {
    if (root ==null) return true;
    return (low == null || root.val > low) && ( high == null || root.val < high)
    && valid(root.left, low, root.val)
    && valid(root,right, root.val, high);
    }

    // OR we can traverse the Tree using inOrder and check whether the array we obtained is
    // monotonically increases.

    Balanced binary Tree

    // Notice that: by counting the tree balanced or not, we should use the height = MAX depth

    public boolean isBalanced(TreeNode root) {
    if(root == null) return true;
    // if Math.abs(maxDepth(root.left) - maxDepth(root.right) > 1) {return false;}
    // return isBalanced(root.left) && isBalanced(root.right);

    return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 
    && isBalanced(root.left) 
    && isBalanced(root.right);
    

    }

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

    // Above approach recalculates max depth for each node repeatedly,
    // we can optimize it by passing the depth bottom up

    public boolean isBalanced(TreeNode root) {
    return maxDepth(root);
    }

    public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    L = maxDepth(root.left);
    if (L == -1) return -1;
    R = maxDepth(root.rigth);
    if (R == -1) return -1;
    return (Math.abs(L - R) <= 1) ? (Math.max(L, R) + 1) : -1;

    }

    相关文章

      网友评论

          本文标题:isValidBST & Balanced binary

          本文链接:https://www.haomeiwen.com/subject/avuaeftx.html