递归——通过二叉搜索树的校验算法解释递归思想

最近学习了覃超老师的算法课程中间有一个看似简单但理解不彻底的算法，写点东西跟大家分享一下：
递归的基础概念就不写了，网上帖子很多。
先抛出一个问题：
Validate Binary Search Tree （校验二叉搜索树）
Given a binary tree, determine if it is a valid binary search tree (BST).（给出一棵树，校验是不是二叉搜索树）
Assume a BST is defined as follows:（二叉搜索树定义）
1.The left subtree of a node contains only nodes with keys less than the node's key.
2.The right subtree of a node contains only nodes with keys greater than the node's key.
3.Both the left and right subtrees must also be binary search trees.

java递归解：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class RecursionSolution {
    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }
        return isBSTHelper(root, null, null);
    }

    private boolean isBSTHelper(TreeNode root, Integer lower, Integer upper) {
        if(lower != null && root.val <= lower) {
            return false;
        }
        if(upper != null && root.val >= upper) {
            return false;
        }
        boolean left = root.left == null ? true : isBSTHelper(root.left, lower, root.val);
        if(left) {
            return root.right == null ? true : isBSTHelper(root.right, root.val, upper);
        } else {
            return false;
        }
    }
}

首先对算法思路做一个基本的解释：
若root为空根据二叉搜索树的定义返回true；
递归方法定义了三个参数：根节点，下边界，上边界；
若上边界有值，根节点值应当小于上边界；
若下边界有值，根节点值应当大于下边界；
根节点左儿子不为空时，将当前节点值设置为上边界值，递归调用左儿子；
根节点右儿子不为空时，将当前节点值设置为下边界值，递归校验右儿子；

看了以上的解释仿佛全是屁话，跟递归调用没有什么关系。最终也没法理解为什么这么写是对的，如果看到现在认为理解了这个算法，那么不妨检验一下，用循环的方式来重写一下这个算法……

递归的本质是一种循环，类似于盗梦空间里的工作方式，在梦境中再进入一层梦境，然后再进入下一层，关键是有一个闹钟能够指引循环，一层一层的依次返回到最外层结束。
理解一下这个调用逻辑图：

微信截图_20181218222117.png

重点理解一下上下边界的递归传递思路：调用左儿子时改变上边界，调用右儿子时改变下边界；（为什么呢？即调用左儿子时下边界是由祖先（某个右祖先）确认的，而该上边界是经过校验合法的！）
理解调用图谱传递是理解递归调用的关键！

下面是一个用迭代实现的：

class IteratorSolution {
    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }

        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> upperStack = new LinkedList<>();
        LinkedList<Integer> lowerStack = new LinkedList<>();
        stack.add(root);
        upperStack.add(null);
        lowerStack.add(null);
        while(!stack.isEmpty()) {
            TreeNode treeNodeTop = stack.poll();
            Integer upper = upperStack.poll();
            Integer lower = lowerStack.poll();
            if(treeNodeTop.right != null) {
                if(treeNodeTop.right.val <= treeNodeTop.val) {
                    //下边界校验
                    return false;
                }
                if(upper != null && upper <= treeNodeTop.right.val) {
                    return false;
                }
                stack.add(treeNodeTop.right);
                lowerStack.add(treeNodeTop.val);
                upperStack.add(upper);
            }

            if(treeNodeTop.left != null) {
                if(treeNodeTop.left.val >= treeNodeTop.val) {
                    return false;
                }
                if(lower != null && lower >= treeNodeTop.left.val) {
                    return false;
                }
                stack.add(treeNodeTop.left);
                upperStack.add(treeNodeTop.val);
                lowerStack.add(lower);
            }

        }
        return true;
    }
}

欢迎诸位拍砖指出错误之处，以免误人子弟。