# 验证二叉搜索树  中序遍历判断二叉查找树 ``` let pre = -Infinity; var isValidBST = function(root) { if(!root) return true; let left = isValidBST(root.left); if(root.val <= pre || !left) return false; pre = root.val; return isValidBST(root.right); }; ``` # 二叉搜索树的第k个结点 给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。  二叉搜索树进行中序遍历，发现结果为1,3,4,5,8,9，其恰好是一个排序好的顺序，因此二叉搜索树也叫做二叉排序树。 **二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。** 所以，按照中序遍历顺序找到第k个结点就是结果。` 非递归中序遍历： [链接](https://blog.csdn.net/billy1900/article/details/86229656) （1）设置一个栈S存放所经过的根结点（指针）信息；初始化S； （2）第一次访问到根结点并不访问，而是入栈； （3）中序遍历它的左子树，左子树遍历结束后，第二次遇到根结点，就将根结点（指针）退栈，并且访问根结点；然后中序遍历它的右子树。 （4） 当需要退栈时，如果栈为空则结束。 ``` function KthNode(pRoot, k) { if(k <= 0){return null;} return inorderTraversal(pRoot, k); } function inorderTraversal (root, k) { if (!root) {return null} let count = 0 let stack = [] while (root || stack.length > 0) { while (root) { stack.push(root) root = root.left } if (stack.length > 0) { root = stack.pop() count++ if (count === k) {return root} root = root.right } } return null }; ``` >递归实现 ``` var kthSmallest = function(root, k) { let res; function midOrder(root){ if(!root) return root; midOrder(root.left); if(k === 0) return res; else{ res = root.val; k--; } midOrder(root.right); } midOrder(root); return res; }; ``` ``` function KthNode(pRoot, k) { var arr=[]; if(pRoot===null||k<1){ return null;} function midInorder(root){ if(root.left!==null){ midInorder(root.left) } arr.push(root); if(root.right!==null){ midInorder(root.right); } } midInorder(pRoot); return arr[k-1]; } ``` # 把二叉搜索树转换为累加树 https://leetcode-cn.com/problems/convert-bst-to-greater-tree/  反中序遍历 ``` var bstToGst = function(root) { let sum = 0 function traversal (root) { if (root !== null) { traversal(root.right) root.val += sum sum = root.val traversal(root.left) } } traversal(root) return root } ``` # 判断数组是否是二叉搜索树 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 二叉查找树，又被称为二叉搜索树。其特点如下：设x为二叉查找树中的一个结点，x节点包含关键字key，一句话就是左孩子比父节点小，右孩子比父节点大，还有一个特性就是”中序遍历“可以让结点有序 ``` function VerifySquenceOfBST(sequence) { if (!sequence.length) {return false} return checkVerify(sequence) } function checkVerify(sequence) { let root = sequence[sequence.length - 1] let i = 0 let leftTree = [] let rightTree = [] for (i; i < sequence.length - 1; i++) { if (sequence[i] > root) { break} leftTree.push(i) } for (i; i < sequence.length - 1; i++) { if (sequence[i] < root) { return false} leftTree.push(i) } if (leftTree.length < 1 && rightTree.length < 1) { return true} return checkVerify(leftTree) && checkVerify(rightTree) } ```