本文主要是介绍程序员面试金典: 检查是否为BST、 寻找下一个结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.检查是否为BST
题目描述
请实现一个函数，检查一棵二叉树是否为二叉查找树。给定树的根结点指针TreeNode* root，请返回一个bool，代表该树是否为二叉查找树。
方法1：二叉树的中序遍历
先用二叉树的中序遍历进行排序，用ArrayList容器来盛结果，最后判断ArrayList是否有序
import java.util.*;/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}*/
public class Checker {ArrayList<Integer> arr=new ArrayList<Integer>();public boolean checkBST(TreeNode root) {if(root==null) return true;checkBSTcore(root);for(int i=0;i+1<arr.size();i++){if(arr.get(i)>arr.get(i+1)){return false;}}return true;}public void checkBSTcore(TreeNode root){if(root==null) return;checkBSTcore(root.left);arr.add(root.val);checkBSTcore(root.right);}
}方法2：每个结点分别和左右比较
import java.util.*;/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}*/
public class Checker {public boolean checkBST(TreeNode root) {return judgetBin(Integer.MIN_VALUE,root,Integer.MAX_VALUE);}private boolean judgetBin(int minValue, TreeNode root, int maxValue) {if(root==null) return true;if(minValue>root.val||maxValue<root.val) return false;//分别判断一棵树的左右两支return judgetBin(minValue,root.left,root.val)&&judgetBin(root.val,root.right,maxValue);}
}2.寻找下一个结点
题目描述
请设计一个算法，寻找二叉树中指定结点的下一个结点（即中序遍历的后继）。
给定树的根结点指针TreeNode* root和结点的值int p，请返回值为p的结点的后继结点的值。保证结点的值大于等于零小于等于100000且没有重复值，若不存在后继返回-1。
方法1：用ArrayList来存
import java.util.*;/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}*/
public class Successor {ArrayList<Integer> list=new ArrayList<Integer>();public int findSucc(TreeNode root, int p) {findPath(root);if(p<0||p>100000) return -1;for(int i=0;i<list.size();i++){if(list.get(i)==p&&i<list.size()-1){return list.get(i+1);}}return -1;}public void findPath(TreeNode root){if(root==null) return;findPath(root.left);list.add(root.val);findPath(root.right);}
}方法2：用队列
import java.util.*;/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}*/
public class Successor {Queue<Integer> queue=new LinkedList<Integer>();public int findSucc(TreeNode root, int p) {if(p<0||p>100000) return -1;findSuccCore(root);while(!queue.isEmpty()){int temp=queue.poll();if(temp==p&&(!queue.isEmpty()))return queue.poll();}return -1;}public void findSuccCore(TreeNode root){if(root==null) return;findSuccCore(root.left);queue.offer(root.val);findSuccCore(root.right);}
}这篇关于程序员面试金典: 检查是否为BST、 寻找下一个结点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
