[Algorithm] BST问题

BST性质：左边都比root小，右边都比root大

BST的中序遍历得到的节点访问顺序是从小到大的顺序

98. Valid Binary Search Tree： 点击打开链接

方法一

思路：先中序遍历BST拿到结果list，遍历list里元素，看当前的元素值是不是小于下一个元素值，只要有当前元素值大于等于下一个元素值的，就返回false

/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: True if the binary tree is BST, or false */ public boolean isValidBST(TreeNode root) { if(root==null){ return true; } List<TreeNode> result=inOrder(root); for(int i=0;i<result.size()-1;i++){ if(result.get(i).val>=result.get(i+1).val){ return false; } } return true; } private List<TreeNode> inOrder(TreeNode root){ List<TreeNode> list=new ArrayList<>(); Stack<TreeNode> stack=new Stack<>(); TreeNode cur=root; while(cur!=null || !stack.isEmpty()){ while(cur!=null){ stack.push(cur); cur=cur.left; } cur=stack.pop(); list.add(cur); cur=cur.right; } return list; } }方法二

思路：递归，边遍历边比较

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isValidBST(TreeNode root) { return helper(root,Long.MAX_VALUE, Long.MIN_VALUE); } public boolean helper(TreeNode root,long maxVal,long minVal){ if(root==null){ return true; } if(root.val>=maxVal || root.val<=minVal){ return false; } return helper(root.left,root.val,minVal) && helper(root.right,maxVal,root.val); } }

11. Search Range in Binary Search Tree:  点击打开链接

思路：中序遍历得到list，再遍历拿到list里每一个符合条件的值 /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of the binary search tree. * @param k1 and k2: range k1 to k2. * @return: Return all keys that k1<=key<=k2 in ascending order. */ public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) { ArrayList<Integer> result=new ArrayList<>(); if(root==null){ return result; } ArrayList<Integer> list=inorder(root); for(int i=0;i<list.size();i++){ if(list.get(i)>=k1 && list.get(i)<=k2){ result.add(list.get(i)); } } return result; } private ArrayList<Integer> inorder(TreeNode root){ ArrayList<Integer> result=new ArrayList<>(); if(root==null){ return result; } Stack<TreeNode> stack=new Stack<>(); TreeNode cur=root; while(!stack.isEmpty() || cur!=null){ while(cur!=null){ stack.push(cur); cur=cur.left; } cur=stack.pop(); result.add(cur.val); cur=cur.right; } return result; } }

173.Binary Search Tree Iterator： 点击打开链接

思路：就是BST中序遍历的拆解形式

/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class BSTIterator { Stack<TreeNode> stack; public BSTIterator(TreeNode root) { stack=new Stack<>(); AddNodeToStack(root); } /** @return whether we have a next smallest number */ public boolean hasNext() { return !stack.isEmpty(); } /** @return the next smallest number */ public int next() { TreeNode cur=stack.pop(); AddNodeToStack(cur.right); return cur.val; } private void AddNodeToStack(TreeNode root){ while(root!=null){ stack.push(root); root=root.left; } } } /** * Your BSTIterator will be called like this: * BSTIterator i = new BSTIterator(root); * while (i.hasNext()) v[f()] = i.next(); */