双非本科准备秋招（22.1）—— 力扣二叉搜索树

本文主要是介绍双非本科准备秋招（22.1）—— 力扣二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、98. 验证二叉搜索树

中序遍历的非递归实现，我们中序遍历二叉搜索树，得到的结果一定是递增的，否则就不是二叉搜索树。

class Solution {public boolean isValidBST(TreeNode root) {//中序LinkedList<TreeNode> stack = new LinkedList<>();LinkedList<TreeNode> list = new LinkedList<>();while(!stack.isEmpty() || root != null){if(root != null){stack.push(root);root = root.left;}else{TreeNode t = stack.pop();list.add(t);root = t.right;}}for(int i = 0; i < list.size()-1; i++){if(list.get(i).val >= list.get(i+1).val){return false;}}return true;}
}

2、938. 二叉搜索树的范围和

改造一下前序遍历，最后一个参数sum就是和，判断node.val的值是否在范围内，如果在范围内，那么就累加到sum中，然后再让sum加上左右子树的sum值即可。

class Solution {public int rangeSumBST(TreeNode root, int low, int high) {return preOrder(root, low, high, 0);}public int preOrder(TreeNode node, int low, int high, int sum){if(node == null){return 0;}if(node.val >= low && node.val <= high){sum += node.val;}sum += preOrder(node.left, low, high, 0) + preOrder(node.right, low, high, 0);return sum;}
}

3、1008. 前序遍历构造二叉搜索树

遍历一下数组，每次都把这个值按照二叉搜索树的性质加入树中。先在树中搜索这个节点的值，因为题目保证不重复，所以肯定搜不到，此时 t 的位置就是待插入的位置，parent是 t 的父节点，如果parent是null，说明为空树，那么root=parent。

然后，将值跟parent的左右子树的val作比较，小于就加在parent左边，大于就加在parent右边。

class Solution {public TreeNode bstFromPreorder(int[] preorder) {TreeNode root = null;for(int i = 0; i < preorder.length; i++){TreeNode t = root;TreeNode parent = null;int val = preorder[i];while(t != null){parent = t;if(val < t.val){t = t.left;}else if(t.val < val){t = t.right;}}TreeNode node = new TreeNode(val);if(parent == null) {root = node;}else if(val < parent.val){parent.left = node;}else if(val > parent.val){parent.right = node;}}return root;}
}

4、530. 二叉搜索树的最小绝对差

要求返回任意二者的最小绝对查，考虑二叉搜索树的性质，如果我们中序遍历，那么遍历的结果一定是升序的，所以最小绝对差肯定是在中序遍历结果的两两之差中找。

直观的想法就是遍历一遍加入数组，再遍历一遍数组。

可以优化一下，定义一个全局TreeNode为pre，默认是null，每次操作完之后，都重新记录一下pre的值，这样我们就能得到之前和现在的节点了。

class Solution {int ans = Integer.MAX_VALUE;TreeNode pre = null;public int getMinimumDifference(TreeNode root) {inOrder(root);return ans;}void inOrder(TreeNode root){if(root == null) return;inOrder(root.left);if(pre != null){ans = Math.min(ans, Math.abs(pre.val - root.val));}pre = root;inOrder(root.right);}
}