700 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

题解

二叉搜索树中中最重要的特征就是他的中序遍历是有序的，所以基本上是围绕着中序遍历去展开的。

题解1

对应此题，最直接的就是中序遍历然后找到val，这里先给出非递归的中序遍历

var searchBST = function (root, val) {
    var searchBSTmiddle = function (root) {
        const stack = []
        let result = null
        if (!root) {
            return result
        }
        stack.push(root)
        while (stack.length) {
            const current = stack.pop()
            if (current) {
                if (current.right) {
                    stack.push(current.right)
                }
                //处理中间节点
                stack.push(current)
                //放null表示要处理该节点
                stack.push(null)
                if (current.left) {
                    stack.push(current.left)
                }
            } else {
                const current = stack.pop()
                if (current.val === val) {
                    result = current
                }
            }
        }

        return result
    }
    return searchBSTmiddle(root)
};

题解2

用递归的方法解答，首先不给任何优化,纯粹的深度优先遍历，遍历过所有节点，然后返回符合条件的节点。

var searchBST = function (root, val) {
    var searchBSTMiddle = function(root, val) {
        if(!root) {
            return root
        }
        if(root.val == val) {
            return root
        }
        const left = searchBSTMiddle(root.left, val)

        const right = searchBSTMiddle(root.right, val)

        return left || right
    }
    return searchBSTMiddle(root, val)
};

利用二叉搜索树的条件进行剪枝。当当前值小于root时，去左子树递归，当当前值大于root时，去右子树递归。

var searchBST = function (root, val) {
    var searchBSTMiddle = function (root, val) {
        if (!root) {
            return root
        }
        if (root.val == val) {
            return root
        }
        let result
        if (root.val > val) {
            result = searchBSTMiddle(root.left, val)
        } else {
            result = searchBSTMiddle(root.right, val)
        }

        return result
    }
    return searchBSTMiddle(root, val)
};