二叉树刷题总结：二叉搜索树的属性

二叉树刷题总结：二叉搜索树的属性

二叉搜索树中的搜索

题目

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

解题思路

二叉搜索树是一棵有序树，它有着以下的这些特征：

左子树上的所有节点的值小于根节点的值；右子树上的所有节点的值大于根节点的值；

于是，我们可以用递归的方式来求解。

代码实现

class Solution { // 递归，利用二叉搜索树特点 public TreeNode searchBST(TreeNode root, int { if (root == null || root.val == val) { return root; } // 如果小于根节点 if (val < root.val) { return searchBST(root.left, val); } else { // 反之 return

时间复杂度：O(H), H 为二叉搜索树的高度。

空间复杂度：O(H), 递归栈的深度为 H。

是不是二叉搜索树

题目

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

解题思路

二叉搜索树有一特性是：在中序遍历下，输出的二叉搜索树节点的数值是一个有序序列。

于是，我们可以通过中序遍历的方式，来判断该序列是否是有序的，从而来判断该二叉树是否是一个有效的二叉树。

代码实现

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public long pre = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if (root == null) { return true; } if (!isValidBST(root.left)){ return false; } if (root.val <= pre) { return false; } pre = root.val; return

时间复杂度 : O(n)，其中 n 为二叉树的节点个数;

空间复杂度 : O(n)，其中 n 为二叉树的节点个数;

求二叉搜索树的最小绝对差

题目

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

解题思路

因为二叉搜索树是一棵有序树，通过中序遍历，我们可以得到一个有序数组，这就转化为在有序数组中求最值。

代码实现

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { int ans; int pre; public int getMinimumDifference(TreeNode root) { ans = Integer.MAX_VALUE; pre = -1; inOrder(root); return ans; } public void inOrder(TreeNode node){ if (node == null) { return; } inOrder(node.left); if (pre == -1) { pre = node.val; } else

时间复杂度：O(n)，其中 n 为二叉搜索树节点的个数。

空间复杂度：O(n), 递归栈的深度为节点数 n。

求二叉搜索树的众数

题目

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

解题思路

对二叉搜索树进行中序遍历，这样就得到了一个有序数组；利用哈希表，来存储有序数组每个元素出现的次数，并记录次数最高的数值 maxLen；遍历哈希表，根据 maxLen，求得出现频率最高元素的合集；

代码实现

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { private List list; public int[] findMode(TreeNode root) { list = new ArrayList(); inOrder(root); Map map = new HashMap(); int maxLen = Integer.MIN_VALUE; for (int value :list) { map.put(value, map.getOrDefault(value, 0) + 1); if (maxLen < map.get(value)) { maxLen = map.get(value); } } if (maxLen > 0) { List ans = new ArrayList<>(); for (int b:map.keySet()) { if (map.get(b).equals(maxLen)) { ans.add(b); } } int answ[] = new int[ans.size()]; for (int i = 0; i < ans.size(); i++) { answ[i] = ans.get(i); } return answ; } return new int[0]; } public void inOrder(TreeNode node){ if (node == null) return; inOrder(node.left); list.add(node.val); inOrder(node.right); }}

时间复杂度：O(n), 即遍历这棵树的复杂度。

空间复杂度：O(n), 即递归的栈空间的空间代价。

最后

好了，关于二叉搜索树的属性到这里就结束了。相信看完这篇文章，你会对二叉搜索树的属性有一定的了解，感谢你的阅读。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。