sing1ee

###leetcode Sqrt(x)

####思路

• 二分查找

####java code

public class Solution {

sing1ee

###leetcode Add Binary

#####思路

• merge sort

#####java code

public class Solution {

sing1ee

###leetcode Rotate List

####思路

• 双指针法：第一个指针先走n+1步，然后一起走，知道第一个指针到终点：
  • 第二个指针的next设置为新的head；
  • 第二个指针的next设置为null；
  • 第一个指针的前一个节点的next指向head；
  • 返回新的head。

####NOTE

sing1ee

###leetcode Restore IP Addresses

####思路

• 树搜索，深度优先
• 剪枝
• 注意路径保存

public class Solution {

sing1ee

###leetcode Reverse Linked List II

####思路

• 遍历每个需要reverse的节点，使其next节点，指向前一个节点。
• 当时最后一个几点，顺着指向next节点，找到reverse的第一个节点，将其next指向后面的不需要reverse的节点。
• 注意边界
• 注意next修改顺序
• 代码不够美，需要改进。

####java code

sing1ee

###leetcode Recover Binary Search Tree

####rationale

• 树的问题，都可以递归解决。
• 有交换数值的节点那么有以下几种情况
• 左边有大于根节点的节点 且 右边有小于根节点的节点
• 仅左边有大于根节点的节点
• 仅右边有小于根节点的节点
• 递归考虑左右子树

sing1ee

###leetcode Binary Tree Inorder Traversal

####思路

• 循环遍历找到树的最左的节点，同时在stack中遍历过的每一个节点。
• 然后从栈顶弹出元素，直到stack为空。将该元素加入结果列表。判断该元素是否有右孩子，如果有，加入到stack中；遍历找到该右孩子的最左节点，都加入stack中，重复循环。

####java代码

sing1ee

###leetcode Validate Binary Search Tree

####思路

• 比较简单：递归。注意，所有左子树的节点值，都小于根节点-》意味着左子树中值最大的节点的val<root.val。最大的节点是哪一个呢？root.left的最右一个节点。右子树类似。

/**
 * Definition for binary tree
 * public class TreeNode {

sing1ee

###leetcode Binary Tree Zigzag Level Order Traversal

####思路

• 每次遍历完一层之后，下一次逆向输出。

####java代码

/**

sing1ee

###leetcode Binary Tree Level Order Traversal II

####Note:

• 用stack存储I中的结果，反序输出。

####代码很简单