98. Validate Binary Search Tree
I. 利用Binary Search Tree的性质 保存对于当前结点应该满足的min和max范围
II. Use the benefit of In-Order Traversal that the sequence retrieved is increasing. Store the pre value and compare.
Left--- Root --- Right
```java
public boolean isValidBST(TreeNode root) {
ArrayList<Integer> pre = new ArrayList<Integer>();
pre.add(null);
return helper(root, pre);
}
private boolean helper(TreeNode root, ArrayList<Integer> pre)
{
if(root == null)
return true;
boolean left = helper(root.left,pre);
if(pre.get(0)!=null && root.val<=pre.get(0))
return false;
pre.set(0,root.val);
return left && helper(root.right,pre);
}
### [270. Closest Binary Search Tree Value](https://leetcode.com/problems/closest-binary-search-tree-value/?tab=Description)
The recursive solution check where the target value possible lies by comparing the root.val with the target and after that compare the difference of the root and target and the closest value of the right/left sub tree. Directly return the root.val if there are no right or left sub tree.
Recursive:
```java
public class Solution {
public int closestValue(TreeNode root, double target) {
TreeNode next = (root.val > target)? root.right:root.left;
if(next == null)return root.val;
int val = closestValue(next,target);
if(Math.abs(target - val) < Math.abs(target - root.val)){
return val;
}
return root.val;
}
}
Iterative:
public class Solution {
public int closestValue(TreeNode root, double target) {
TreeNode p = root;
int res = p.val;
while(p != null){
if(Math.abs(p.val - target) < Math.abs(res - target)){
res = p.val;
}
p = (p.val > target)? p.left:p.right;
}
return res;
}
}
116. Populating Next Right Pointers in Each Node
弄清楚过程 并不是BFS 指针每一层逐一处理 提前保存好下一行的开始指针
public class Solution {
public void connect(TreeLinkNode root) {
//corner
if(root==null)return;
TreeLinkNode cur = root;
TreeLinkNode firstLeft = null;
while(cur.left!=null){
//下一行的起点
firstLeft = cur.left;
//平衡移动
while(cur!=null){
cur.left.next = cur.right;
cur.right.next = cur.next==null? null:cur.next.left;
cur = cur.next;
}
cur = firstLeft;
}
}
}
117. Populating Next Right Pointers in Each Node II
本质上还是遍历 只不过不在原来的Queue里面 用指针操作 记录上一层的Head Node 同时由于不是完全二叉树 所以每一层的起始节点应该为第一个不是Null的节点 两层循环 每次循环之后重置起始节点
public class Solution {
public void connect(TreeLinkNode root) {
TreeLinkNode lastFirst = root;
TreeLinkNode curFirst = null;
//The current pointer
TreeLinkNode p = null;
while(lastFirst != null){
TreeLinkNode lastCur = lastFirst;
while(lastCur != null){
if(lastCur.left!=null){
//check whether the current first is assigned
if(curFirst == null){
curFirst = lastCur.left;
p = curFirst;
}
else{
p.next = lastCur.left;
p = p.next;
}
}
//the same procedure when encounter a right
if(lastCur.right != null){
if(curFirst == null){
curFirst = lastCur.right;
p = curFirst;
}
else{
p.next = lastCur.right;
p = p.next;
}
}
lastCur = lastCur.next;
}
lastFirst = curFirst;
curFirst = null;
}
}
}
255. Verify Preorder Sequence in Binary Search Tree
没有思路。。
做法I 维护一个最小值 min 其先序遍历的结果是{5, 2, 1, 3, 6}, 我们先设一个最小值low，然后遍历数组，如果当前值小于这个最小值low，返回false，对于根节点，我们将其压入栈中，然后往后遍历，如果遇到的数字比栈顶元素小，说明是其左子树的点，继续压入栈中，直到遇到的数字比栈顶元素大，那么就是右边的值了，我们需要找到是哪个节点的右子树，所以我们更新low值并删掉栈顶元素，然后继续和下一个栈顶元素比较，如果还是大于，则继续更新low值和删掉栈顶，直到栈为空或者当前栈顶元素大于当前值停止，压入当前值，这样如果遍历完整个数组之前都没有返回false的话，最后返回true即可，参见代码如下：
public class Solution {
public boolean verifyPreorder(int[] preorder) {
int min=Integer.MIN_VALUE;
Stack<Integer> stack = new Stack();
int len = preorder.length;
if(len == 0||len == 1){
return true;
}
for(int i = 0;i < len;i++){
int val = preorder[i];
if(val < min){
return false;
}
while(!stack.empty()&& val > stack.peek()){
min = stack.pop();
}
stack.push(val);
}
return true;
}
}