ValidateBinarySearchTree [source code]

public class ValidateBinarySearchTree {
static
/******************************************************************************/
class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;    // no idea why
        return dfs (root).is_valid;
    }

    Values dfs (TreeNode root) {
        Values left = null, right = null;
        if (root.left != null)
            left = dfs (root.left);
        if (root.right != null)
            right = dfs (root.right);
        // Critical: initial value as ROOT.VAL
        Values res = new Values (root.val, root.val);
        if (left != null) {
            if (!left.is_valid || left.max >= root.val) {
                res.is_valid = false;
                return res;
            }
            res.min = Math.min (res.min, left.min);
        }
        if (right != null) {
            if (!right.is_valid || right.min <= root.val) {
                res.is_valid = false;
                return res;
            }
            res.max = Math.max (res.max, right.max);
        }
        return res;
    }

    static class Values {
        int min, max;
        boolean is_valid = true;
        Values (int a, int b) {min = a; max = b; }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ValidateBinarySearchTree.Solution tester = new ValidateBinarySearchTree.Solution();
    }
}

一个直观的想法肯定是, 直接走一个InOrder traversal, 然后看看是不是sorted; 但是问题来了, 这个inorder traversal sorted只是一个必要条件, 是一个充分条件吗? 看看AC rate这么惨, 感觉是有坑;

既然你想要一个更强的充分条件, 那么直接就回忆定义; BST的定义, 用root level decision的观点来理解, 就是么一个root, 要比自己left subtree全都大, 比right subtree全都小; 那么自然带来的一个思路, 就是每一个node维护自己的subtree的最大值最小值就行了; 更进一步, 我们完全可以在一个PostOrder的过程当中直接把这两个最值返回上去到root, 这样就不用维护了, 一个DFS就可以搞定;

最后大概写写, 还是AC了, 代码实际的实现细节还是有点小讲究的; 一开始, 我用的是leaf判断, 在Null直接返回一个[MAX, MIN]上去:

被这个case给break掉之后发现很难处理; 然后决定用pre leaf的判断处理, 不过pre leaf判断的思路也有问题; 就是核心逻辑要有各种对Null的guard; 一个关键的细节是上面comment标注出来的res的初始值; 这个刚开始半天还真的没有想到; default init value + conditional update的思路在Pintos的lab2当时已经见识过了, 这里有一次看到了这种思路处理的重要性;

最后速度是8ms (2%), 不是很理想, 不知道为什么, 按理说我这个就是一个DFS, 还能有多快? 难道traversal那个方法是对的?

精简改写了一下, 速度直接到了3(24), 也是很玄学:

class Solution {  
    public boolean isValidBST(TreeNode root) {  
        return root != null ? dfs (root).is_valid : true;  
    }  

    Values dfs (TreeNode root) {  
        Values left = null, right = null, res = new Values (root.val, root.val);  
        if (root.left != null) {  
            left = dfs (root.left);  
            if (!left.is_valid || left.max >= root.val) {  
                res.is_valid = false;  
                return res;  
            }  
            res.min = Math.min (res.min, left.min);  
        }  
        if (root.right != null) {  
            right = dfs (root.right);  
            if (!right.is_valid || right.min <= root.val) {  
                res.is_valid = false;  
                return res;  
            }  
            res.max = Math.max (res.max, right.max);  
        }  
        return res;  
    }  

    static class Values {  
        int min, max;  
        boolean is_valid = true;  
        Values (int a, int b) {min = a; max = b; }  
        Values () {}  
    }  
}

没有editorial;

https://leetcode.com/problems/validate-binary-search-tree/discuss/32112/Learn-one-iterative-inorder-traversal-apply-it-to-multiple-tree-questions-(Java-Solution)

I will show you all how to tackle various tree questions using iterative inorder traversal. First one is the standard iterative inorder traversal using stack. Hope everyone agrees with this solution.

Question : Binary Tree Inorder Traversal

public List<Integer> inorderTraversal(TreeNode root) {  
    List<Integer> list = new ArrayList<>();  
    if(root == null) return list;  
    Stack<TreeNode> stack = new Stack<>();  
    while(root != null || !stack.empty()){  
        while(root != null){  
            stack.push(root);  
            root = root.left;  
        }  
        root = stack.pop();  
        list.add(root.val);  
        root = root.right;  

    }  
    return list;  
}

Now, we can use this structure to find the Kth smallest element in BST.

Question : Kth Smallest Element in a BST

public int kthSmallest(TreeNode root, int k) {  
    Stack<TreeNode> stack = new Stack<>();  
    while(root != null || !stack.isEmpty()) {  
        while(root != null) {  
            stack.push(root);      
            root = root.left;     
        }   
        root = stack.pop();  
        if(--k == 0) break;  
        root = root.right;  
    }  
    return root.val;  
}

We can also use this structure to solve BST validation question.

Question : Validate Binary Search Tree

public boolean isValidBST(TreeNode root) {  
   if (root == null) return true;  
   Stack<TreeNode> stack = new Stack<>();  
   TreeNode pre = null;  
   while (root != null || !stack.isEmpty()) {  
      while (root != null) {  
         stack.push(root);  
         root = root.left;  
      }  
      root = stack.pop();  
      if(pre != null && root.val <= pre.val) return false;  
      pre = root;  
      root = root.right;  
   }  
   return true;  
}

大概还是能记得这个traversal的写法的, header是两个or起来的条件, 然后body内部是先推大梁, 然后pop, visit, 然后向右移动; 因为是先推大梁, 所以可以利用Stack的pop顺序来完成root.left before root;

另外, 看来直接traversal验证是可以的; 那么你能证明吗? 好像也不难证明啊, 找到lowest subtree that first returned invalid, 那么这个root的left肯定比root自己大, 那么这俩反正在traversal里面是.. root.left root ..这样的关系, 最后的traversal肯定就不会sorted;

但是想到一个问题, 我们知道了用InOrder traversal的方法是可以的, 但是区分这个方法跟serialize的区别! traversal方法一般是用一个prev来实现的, 而不是先全部serialize, 然后最后给这个serialize出来的array再单独来一个pass;

https://leetcode.com/problems/validate-binary-search-tree/discuss/32109/My-simple-Java-solution-in-3-lines

public class Solution {  
    public boolean isValidBST(TreeNode root) {  
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);  
    }  

    public 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);  
    }  
}

Basically what I am doing is recursively iterating over the tree while defining interval for each node which value must fit in.

很有意思的一个想法哈, 我的想法是, child将自己的subtree的最值向上传递, 利用DFS的Bottom-Up的性质; 他这里的思路则不同, 是把一个上下限的limit向下传递给child; 最后验证的内容实际上是跟我一样的, 不过实现起来简洁很多;

另外注意, 既然是用这个Top-Down的思路, 他这里DFS的方式就是PreOrder而不是PostOrder了;

好像有溢出处理的问题? 好像可能有对这些最值进行test的:

Does it work when the smallest node has the value Integer.MIN_VALUE or the largest node has the value Integer.MAX_VALUE?

Your solution can not pass this case:[ Long.MIN_VALUE , null , Long.MAX_VALUE ]

We can use Object Integer and null pointer to avoid the corner cases (when node has value Integer.MIN_VALUE or Integer.MAX_VALUE ).

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

public boolean isValidBST(TreeNode root) {  
    return help(root, null, null);  
}

这个也就是所有special value思路的一个通病;

这个解法则是直接炮轰用正负无穷的做法:

https://leetcode.com/problems/validate-binary-search-tree/discuss/32104/C++-in-order-traversal-and-please-do-not-rely-on-buggy-INT_MAX-INT_MIN-solutions-any-more

class Solution {  
public:  
    bool isValidBST(TreeNode* root) {  
        TreeNode* prev = NULL;  
        return validate(root, prev);  
    }  
    bool validate(TreeNode* node, TreeNode* &prev) {  
        if (node == NULL) return true;  
        if (!validate(node->left, prev)) return false;  
        if (prev != NULL && prev->val >= node->val) return false;  
        prev = node;  
        return validate(node->right, prev);  
    }  
};

Update:

If we use in-order traversal to serialize a binary search tree, we can
get a list of values in ascending order. It can be proved with the
definition of BST. And here I use the reference of TreeNode
pointer prev as a global variable to mark the address of previous node in the
list.

“In-order Traversal”:
https://en.wikipedia.org/wiki/Tree_traversal#In-order
If you know what INT_MAX or INT_MIN is, then it is no excuse for your carelessness.

long也不是避免问题的解决办法;

Why rely on LLONG_MIN? Don’t you think if you are in a true interview, the next question the interviewer will ask, “okay I have changed my input type to long” then? I am sorry but using long limit to such question is like taking shortcut to just get your answer accepted and won’t help you in real interview.

反正还是要看题目和具体的面试要求; 有些题目其实不用正负无穷还挺难写的;

改写:

public class Solution {  
    TreeNode pre = null;  
    public boolean isValidBST(TreeNode root) {  
        if (root == null) return true;  
        if (!isValidBST(root.left)) return false;  
        if (pre != null && pre.val >= root.val) return false;  
        pre = root;  
        return isValidBST(root.right);  
    }  
}

https://leetcode.com/problems/validate-binary-search-tree/discuss/32141/C++-simple-recursive-solution

bool isValidBST(TreeNode* root) {  
    return isValidBST(root, NULL, NULL);  
}  

bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {  
    if(!root) return true;  
    if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val)  
        return false;  
    return isValidBST(root->left, minNode, root) && isValidBST(root->right, root, maxNode);  
}

这个跟之前那个上下限的方法好像是一样的;

submission最优解: 1(42):

class Solution {  
    public boolean isValidBST(TreeNode root) {  
        return util(root, Long.MAX_VALUE, Long.MIN_VALUE);  
    }  

    private boolean util(TreeNode root, long up, long down){  
        if(root==null)  
            return true;  
        if( !(root.val<up&&root.val>down))  
            return false;  
        if(util(root.left, (long)root.val, down) && util(root.right, up, (long)root.val))  
            return true;  
        return false;  
    }  
}

还是类似的上下限Top-Down的思路;

Problem Description

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

    2  
   / \  
  1   3

Binary tree [2,1,3], return true.

Example 2:

    1  
   / \  
  2   3

Binary tree [1,2,3], return false.

Difficulty:Medium
Total Accepted:220K
Total Submissions:917.1K
Contributor:LeetCode
Companies
facebookmicrosoftamazonbloomberg
Related Topics
treedepth-first search
Similar Questions
Binary Tree Inorder TraversalFind Mode in Binary Search Tree