二叉搜寻树

性质:
1.对于BST的每一个节点node,左子树节点的值都比node的值要小，右子树的值都比node的值大
2.对于BST的每一个节点node,它的左侧子树和右侧子树都是BST。
从算法题的角度来看BST，除了它的定义，还有一个重要的性质:BST的中序遍历后果是有序的

void traverse(TreeNode root){if(root==null){return;}traverse(root.left);//中序遍历代码地位print(root.val);traverse(root.right);}

寻找第Ｋ小的元素\

思考每个根节点须要干什么，节点须要遍历本人时就将rank值加１，代表遍历到了第rank小的节点

int res=0;int rank=0;int kthSmallest(TreeNode root,int k){traverse(root,k);return res;}

二叉搜寻树转换为累加树

节点须要将本人的值更新为res,res代表以后从大到小的节点值的和

public void traverse(TreeNode root){if(root==null){return;}traverse(root.right);res+=root.val;root.val=res;traverse(root.left);}