LeetCode ---- 98、驗證二叉搜尋樹

題目連結

思路：

二叉搜尋樹有一個特性，當使用中序周遊來周遊二叉搜尋樹時，周遊結果一定是一個升序的結果

利用這個特性，改造二叉樹的中序周遊即可，在中序周遊列印目前節點值時，進行與之前最後一次列印的值進行比較即可

public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode pre = null;
        while (!stack.isEmpty() || root != null) {
            if (root != null) { // 目前節點不空，入棧，轉向左子樹
                stack.addFirst(root);
                root = root.left;
            } else {         // 目前節點為空，棧頂元素左子樹為空或已經周遊過，彈出并比較
                root = stack.removeFirst();
                if (pre != null && pre.val >= root.val) {
                    return false;
                }
                pre = root;
                root = root.right;
            }
        }
        return true;
    }
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }