ARTICLE DETAIL

建站实战干货

来自一线的建站与推广经验沉淀，每一条都经过真实交付验证。

首页 / 资讯中心 / 正文

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

2026/9/24 15:47:57 拓冰建站 浏览量
二叉搜索树|不同、验证、转换等

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

文章目录

    • 二叉搜索树|不同、验证、转换等
      • [96 不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees/description/)
      • [98 验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree/description/)
      • [538 把二叉搜索树转换为累加树](https://leetcode.cn/problems/convert-bst-to-greater-tree/description/)

96 不同的二叉搜索树

在这里插入图片描述

  • 参考力扣官方题解，链接：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];}
}

98 验证二叉搜索树

在这里插入图片描述

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

在这里插入图片描述

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;}
}

538 把二叉搜索树转换为累加树

在这里插入图片描述

在这里插入图片描述

  • 法一：递归，右中左遍历
  • 法二：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;}}