二叉搜索树|不同、验证、转换等

• 参考力扣官方题解，链接：https://leetcode.cn/problems/unique-binary-search-trees/solutions/329807/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/
• G(n) = sum(G(i-1)·G(n-i))
• G(2)=G(0)·G(1)+G(1)·G(0)
• G(3)=G(0)·G(2)+G(1)·G(1)+G(2)·G(0)

/*** 不同的二叉搜索树* 参考力扣官方题解，链接：https://leetcode.cn/problems/unique-binary-search-trees/solutions/329807/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/* G(n) = sum(G(i-1)·G(n-i))* G(2)=G(0)·G(1)+G(1)·G(0)* G(3)=G(0)·G(2)+G(1)·G(1)+G(2)·G(0)*/
public class $96 {public int numTrees(int n) {int[] G = new int[n+1];G[0] = 1;G[1] = 1;for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++) {G[i] += G[j-1] * G[i-j];// System.out.println("G  " + i + " " + j + " " + (j-1) + " " + (i-j));}}return G[n];}
}

• 法一：递归
• 法二：中序遍历得到的结果是升序的

import java.util.Stack;/*** 验证二叉搜索树* 法一：递归* 法二：中序遍历得到的结果是升序的*/
public class $98 {//法一：递归public boolean isValidBST(TreeNode root) {return process(root, Long.MIN_VALUE, Long.MAX_VALUE);}private boolean process(TreeNode node, long lower, long upper) {if (node == null) {return true;}if (node.val <= lower || node.val >= upper) {return false;}return process(node.left, lower, node.val) && process(node.right, node.val, upper);}
}

import java.util.Stack;/*** 验证二叉搜索树* 法一：递归* 法二：中序遍历得到的结果是升序的*/
public class $98 {//法二；中序遍历得到的结果是升序的public boolean isValidBST2(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;double prev =  -Double.MAX_VALUE;while (true) {while (cur != null) {stack.push(cur);cur = cur.left;}if (stack.isEmpty()) {break;}TreeNode tmp = stack.pop();if (tmp.val <= prev) return false;prev = tmp.val;cur = tmp.right;}return true;}
}

• 法一：递归，右中左遍历
• 法二：morris反序中序遍历

/*** 把二叉搜索树转换为累加树* 法一：递归，右中左遍历* 法二：morris反序中序遍历*/
public class $538 {//法一：递归，右中左遍历int sum = 0;public TreeNode convertBST(TreeNode root) {if (root == null) {return null;}convertBST(root.right);sum += root.val;root.val = sum;convertBST(root.left);return root;}
}

/*** 把二叉搜索树转换为累加树* 法一：递归，右中左遍历* 法二：morris反序中序遍历*/
public class $538 {//法二：morris反序中序遍历public TreeNode convertBST2(TreeNode root) {int sum = 0;TreeNode cur = root;TreeNode prev = null;while (cur != null) {prev = cur.right;if (prev != null) {while (prev.left != null && prev.left != cur) {prev = prev.left;}if (prev.left == null) {prev.left = cur;cur = cur.right;} else {prev.left = null;sum += cur.val;cur.val = sum;cur = cur.left;}} else {sum += cur.val;cur.val = sum;cur = cur.left;}}return root;}}