最基本的 Preorder, Inorder, Postorder Traverse
Binary Tree Preorder traverse (用stack模拟，先进去right ，再进去left）
Binary Tree Inorder traverse （用stack模拟，每次push整个左枝的所有node，再变换到右边);
Binary Tree Postorder traverse (用stack模拟，跟preorder一样，只是左右的顺序不一样，最后我们可以反过来记录，这样就把原来的问题转换成了一个我熟知的类似于preoder traverse的问题, 记住linkedlist需要addFirst，才能每次O(1)加到前面;)
Kth Smallest Element in a BST (就是inorder的翻版，记录一下count = k就可以了);
Inorder Successor in BST ( Time Complexity: O(logK). 先遍历找到P，同时记录一下左拐的点, 然后如果有右儿子，就扎到最右边的最左下的node，如果没有右儿子，就是找到这个点最后一个左拐的点）
Inorder Successor in BST II (如果有右边节点，那么往右走，右边的最左边node就是答案。如果没有右边的node，那么向上找到第一个左拐的node，就是答案)
Validate Binary Search Tree (用stack来模拟inorder，然后记录pre node，如果pre node >= curnode return false; ) 这里注意的是stack 模拟为什么好？就是dfs是用的call stack，很容易stackoverflow，如果是用stack的话，那么就是利用heap来做 simulation，那样就很大，不会爆栈);
Construct Binary Tree from Preorder and Inorder Traversal (用preorder的root，去找inorder的root，确定leftsize大小，递归即可）
Construct Binary Tree from Inorder and Postorder Traversal (用postorder的最后一个root 去inorder里面找root，确定leftsize, 递归)
Construct Binary Search Tree from Preorder Traversal (用queue的思想，current, left, right，每次安排下一个值，是左边还是右边即可，也就是用lower, upper来确定范围；这题跟Validate Binary Search Tree很类似；也跟 Serialize and Deserialize BST 原理一模一样；O(N);)
Construct Binary Tree from Preorder and Postorder Traversal
总体思想跟inorder的那两题很类似，但是这里因为是binary tree，没有大小的区分，只有相对位置，那么，这题跟上面两题的区别就是如何不用current来找leftsize，
Preorder: current, left, right : 1, (2, 4, 5 ), (3,6,7)
Postorder: left, right, current: (4,5,2), (6,7,3), 1
那么破题口是在2上面，pre[pstart + 1] 在postorder 里面是left的最后一个index，从而可以根据这个算出leftsize
注意要判断pstart == pend的情况；
Validate Binary Search Tree ( 思路1：就是利用BST的性质，左边的不能>= 右边的，那么就是一个inorder traverse 为什么用非递归更好？如果用递归，我们是要用内存中的call-stack来做，它是一个size-limited memory area，如果调用很多很多次，容易stackOverFlow exception 但是用iteration做，使用数据结构中的stack，是在heap上，这样，在stack上消耗的空间是trivial的，我们不用change the total space consumption，而是把space consumption 从stack移到了heap上。 思路2： 用traverse的方法， lower bound 和upper bound 来确定是否valid，注意参数需要使用用Long来表示，防止nodeval 本身就是Integer.MAX_VALUE, Integer.MIN_VALUE；)
Closest Binary Search Tree Value I (这里要知道找target，不会走完所有的node，是个logn的走法，最后肯定走到一个null，然后退出，这里记录一下upper和lower，然后在upper和lower里面pick up一个最接近target的值)
Closest Binary Search Tree Value II (这题考察的很多，不亏是google的题目。其实想明白了很简单，就是：inorder travel的stack方法如果会写的话，怎么找target临近的k个值，也就是用个queue来找。
因为inorder travel得到的值的是从小到大的值，所以就相当于在一个连续的array里面找target 附近的k个值，那么就用一个queue来存储这k个值，然后每次加进来的值，跟queue头的元素，进行比较，如果 math.abs(node.val - target) < Math.abs(queue.peek().val - target) node和target的距离比queue头元素与target的距离要小，说明queue头是比node要小的，所以poll头元素，将新的node加入队列尾部，然后继续移动，如果哪次新加进来的node与target距离比头元素与target距离还要大，那么直接break掉，因为后面的node距离只可能更大，因为我们是inorder travel。有时候，觉得google的题，只要掌握了基本的算法和原理，稍微拐弯一下就可以想到更好的解法，这就是google的题目的优点，特别具有区分度。不难，大家都可以做，但是做出来都不一样。O(n);
/**
* 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 {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> res = new ArrayList<>();
if(root == null) {
return res;
}
Queue<Integer> queue = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
pushLeft(stack, root);
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
if(queue.size() < k) {
queue.offer(node.val);
} else {
if(Math.abs(node.val - target) < Math.abs(queue.peek() - target)) {
queue.poll();
queue.offer(node.val);
} else {
break;
}
}
if(node.right != null) {
pushLeft(stack, node.right);
}
}
return new ArrayList<Integer>(queue);
}
private void pushLeft(Stack<TreeNode> stack, TreeNode node) {
while(node != null) {
stack.push(node);
node = node.left;
}
}
}
思路2：O(logn + k); 分别用prestack和nextstack，来记录找到target过程中的点，然后根据diff来进行 next++, pre--的操作，这里涉及到inorder的next和pre的写法，next就是stack push 右边left的点，反过来，pre就是stack push左边 right的点；
/**
* 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 {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> prestack = new Stack<>();
Stack<TreeNode> nextstack = new Stack<>();
TreeNode node = root;
while(node != null) {
if(node.val < target) {
prestack.push(node);
node = node.right;
} else {
// node.val > target;
nextstack.push(node);
node = node.left;
}
}
int count = 0;
while(count < k) {
double prediff = prestack.isEmpty() ? Integer.MAX_VALUE : (Math.abs(prestack.peek().val - target));
double nextdiff = nextstack.isEmpty() ? Integer.MAX_VALUE : (Math.abs(nextstack.peek().val - target));
if(prediff < nextdiff) {
res.add(prestack.peek().val);
gopre(prestack);
count++;
} else {
res.add(nextstack.peek().val);
gonext(nextstack);
count++;
}
}
return res;
}
private void gonext(Stack<TreeNode> stack) {
TreeNode node = stack.pop();
if(node.right != null) {
node = node.right;
while(node != null) {
stack.push(node);
node = node.left;
}
}
}
private void gopre(Stack<TreeNode> stack) {
TreeNode node = stack.pop();
if(node.left != null) {
node = node.left;
while(node != null) {
stack.push(node);
node = node.right;
}
}
}
}
Serialize and Deserialize BST (用queue来做，O(n); 就是传参的时候用Integer.MIN_VALUE 和Integer.MAX_VALUE来作为下限和上限；只serialize有value的node，不管null node；这样如果value不在lower, upper范围之内，那么就是return null;)
Serialize and Deserialize Binary Tree (用preorder traverse，current，left, right来serialize，然后用queue来deserilize，这题跟BST不同的是，这里需要serilize NULL，因为BST有大小关系，这里没有，所以需要满树才行；而且这里就不需要Integer.MAX_VALUE和Integer.MIN_VALUE作为参数来判断是否return null了，这个复杂度是O(N);)
Serialize and Deserialize N-ary Tree 思路：做这个题目之前，先明白 Serialize and Deserialize Binary Tree 和 Serialize and Deserialize BST 区别和异同，Serialize and Deserialize Binary Tree 因为是BT，没有相互之前的大小关系，所以要serialize full tree，连NULL都要serialize进去，但是BST不同，BST有左右的大小关系，所以只用serialize 有value的node就行，两个都是用queue来serialize，然后用queue来build。N-ary Tree跟BT不同的是，他有children；不能用preorder去serilize，只能用level order去serilize。不同的是，N-ary后面有child的size信息，我们也serilize进去，那么desrilize的时候，用两个queue，一个存当前node的queue，一个存node的child size信息，那么，如果size是n，那么后面2 * n个string，都是当前node的child；每个node都有自己的child信息；Serilize用level order，(跟BT不一样, BT是用)一行一行的serilize，deserilize也是一层一层的build；
![常用的排序算法的空间复杂度和时间复杂度[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)