BST相关题目
二叉搜索树中的众树二叉搜索树节点最小距离两数之和 IV - 输入二叉搜索树总结
二叉搜索树中的众树
501.二叉搜索树中的众树
解题思路：中序遍历二叉搜索树，使得结果集是有序的，过程中将众数个数保存下来。利用两个变量，一个记录当前相同众数数的个数，一个记录众数数的个数。 虽然题目没要求返回众数集的元素顺序，但这最后返回的是按升序来的，因为中序遍历得出的是有序的。
/**
* 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 int curCnt = 1;// 记录当前众数最大个数
private int maxCnt = 1;// 记录总的最大众数最大个数
private TreeNode preNode = null;// 记录前一个节点(中序遍历前一个节点，并非父节点)
public int[] findMode(TreeNode root) {
List
inOrder(numList,root);
int[] ans = new int[numList.size()];
int index = 0;
for(Integer num:numList)
ans[index++] = num;
return ans;
}
private void inOrder(List
if(node==null) return;
inOrder(numList,node.left);
if(preNode!=null){
if(preNode.val==node.val)
curCnt++;
else
curCnt = 1;
}
if(curCnt>maxCnt){
maxCnt = curCnt;
numList.clear();
numList.add(node.val);
}else if(curCnt==maxCnt){
numList.add(node.val);
}
preNode = node;
inOrder(numList,node.right);
}
}
测试：
二叉搜索树节点最小距离
783.二叉搜索树节点最小距离
解题思路：两节点最短距离，肯定是相邻的两个节点，中序遍历升序的情况下即可遍历出最短距离了。和上面一题一样，设置一个 preNode 变量表示中序列的前一个节点。
/**
* 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 int cutDis = (int)1e5;// 记录当前的两节点的距离
private int minDis = (int)1e5;// 记录最小俩节点的距离
private TreeNode preNode = null;// 表示前一个节点
public int minDiffInBST(TreeNode root) {
inOrder(root);
return minDis;
}
private void inOrder(TreeNode node){
if(node==null) return;
inOrder(node.left);
if(preNode!=null)
cutDis = node.val - preNode.val;
if(minDis>cutDis)
minDis = cutDis;
preNode = node;
inOrder(node.right);
}
}
测试：
两数之和 IV - 输入二叉搜索树
653. 两数之和 IV - 输入二叉搜索树
解题思路：中序遍历 + 双指针；这里的双指针用法是：左指针指向的数与右指针指向的数的和与实际值比较，如何比实际值大右指针就向左移一位，反之左指针向右移一个。
/**
* 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
public boolean findTarget(TreeNode root, int k) {
inOrder(root);
Integer[] test = new Integer[0];
Integer[] nums = list.toArray(test);// 个人喜欢数组，这里可以不转换
int l=0, r=nums.length-1;
while(l if(nums[l]+nums[r] ++l; else if(nums[l]+nums[r]>k) --r; else return true; } return false; } private void inOrder(TreeNode node){ if(node==null) return; inOrder(node.left); list.add(node.val); inOrder(node.right); } } 测试： 总结 对二叉搜索树（BST）算法题来说，插入多半用不到（因为人本身会插好藍），常用的还得是（中序）遍历， 搜索，删除都用的少。二叉搜索树无非就是二分法的最好体现，将值小的放左边，将值大的放右边。 （常用）将遍历得到的序列 + 其他算法解题。 精彩链接
您阅读本篇文章共花了：
发表评论