主题：二叉树
（1）111. 二叉树的最小深度（2）113. 路径总和 II（3）116. 填充每个节点的下一个右侧节点指针（4）725. 分隔链表（5）173. 二叉搜索树迭代器（错1）（6）199. 二叉树的右视图（7）222. 完全二叉树的节点个数（8）236. 二叉树的最近公共祖先（错1）（9）257. 二叉树的所有路径（10） 337. 打家劫舍 III（错1）
主题：二叉树 （1）111. 二叉树的最小深度思路：递归
class Solution {
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
int left = 1+minDepth(root.left);
int right = 1+minDepth(root.right);
if(left == 1){
return right;
}else if(right == 1){
return left;
}
return (left < right) ? left:right;
}
}
（2）113. 路径总和 II
思路：递归，注意：对于保存前面节点的list与输入的list不能是同一个，故需要先将输入的list复制一遍。。。但效率太低。
class Solution {
List> res = new ArrayList>();
public List> pathSum(TreeNode root, int targetSum) {
List record = new ArrayList();
findSum(root,targetSum,record);
return res;
}
public void findSum(TreeNode root, int targetSum, List record){
List list = new ArrayList();
for(int i = 0; i < record.size(); i++){
list.add(record.get(i));
}
if(root == null){
return;
}
if(root.val == targetSum && root.right == null && root.left == null){
list.add(root.val);
res.add(list);
return;
}
list.add(root.val);
if(root.left != null){
findSum(root.left, targetSum-root.val, list);
}
if(root.right != null){
findSum(root.right, targetSum-root.val, list);
}
}
}
优化：使用linkedList存储节点值，添加当前节点输入到下一阶段的方法之后，将节点删除，就可以不用再复制list了。
（3）116. 填充每个节点的下一个右侧节点指针class Solution {
public Node connect(Node root) {
if(root == null){
return root;
}
List list = new linkedList();
list.add(root);
while(list.size() != 0){
list = getChild(list);
}
return root;
}
public List getChild(List list){
if(list.size() == 0){
return list;
}
List temp = new linkedList();
for(int i = 0; i < list.size(); i++){
Node node = list.get(i);
if(i != (list.size()-1)){
node.next = list.get(i+1);
}
if(node.left != null){
temp.add(node.left);
temp.add(node.right);
}
}
return temp;
}
}
（4）725. 分隔链表
思路：计算出每个分链表的长度，写一个方法获取链表的前n个，返回包含前n个节点的链表和剩余的链表；
class Solution {
public ListNode[] splitListToParts(ListNode head, int k) {
ListNode[] res = new ListNode[k];
int len = 0;
ListNode cur = head;
while(cur != null){
cur = cur.next;
len++;
}
int sur = len % k;
int listLen = len / k;
for(int i = 0;i < k; i++){
if(i < sur){
ListNode[] temp = getPart(head, listLen + 1);
res[i] = temp[0];
head = temp[1];
}else{
ListNode[] temp = getPart(head, listLen);
res[i] = temp[0];
head = temp[1];
}
}
return res;
}
public ListNode[] getPart(ListNode head, int len){
ListNode[] list = new ListNode[2];
if(len == 0){
return list;
}
ListNode cur = head;
ListNode part = head;
for(int i = 0; i < len-1; i++){
cur = cur.next;
}
head = cur.next;
if(cur != null){
cur.next = null;
}
list[0] = part;
list[1] = head;
return list;
}
}
（5）173. 二叉搜索树迭代器（错1）
题解思路1：将BST按中序改为链式结构；
注意：记住如何改为链式结构的方法；
class BSTIterator {
TreeNode list = null;
public BSTIterator(TreeNode root) {
parseTree(root);
}
public int next() {
int val = list.val;
list = list.right;
return val;
}
public boolean hasNext() {
if(list != null){
return true;
}
return false;
}
public void parseTree(TreeNode node){
if(node.right != null){
parseTree(node.right);
}
node.right = list;
list = node;
if(node.left != null){
parseTree(node.left);
}
}
}
（6）199. 二叉树的右视图
我的思路：先获取每一层的节点list，取list中的最后一个节点值。
class Solution {
public List rightSideView(TreeNode root) {
linkedList list = new linkedList();
List res = new ArrayList();
if(root == null){
return res;
}
list.add(root);
while(list.size() > 0){
res.add(list.peekLast().val);
list = getChild(list);
}
return res;
}
public linkedList getChild(linkedList list){
linkedList child = new linkedList();
for(TreeNode node: list){
if(node.left != null){
child.add(node.left);
}
if(node.right != null){
child.add(node.right);
}
}
return child;
}
}
题解思路：dfs
class Solution {
public List rightSideView(TreeNode root) {
Map rightmostValueAtDepth = new HashMap();
int max_depth = -1;
Deque nodeStack = new ArrayDeque();
Deque depthStack = new ArrayDeque();
nodeStack.push(root);
depthStack.push(0);
while (!nodeStack.isEmpty()) {
TreeNode node = nodeStack.pop();
int depth = depthStack.pop();
if (node != null) {
// 维护二叉树的最大深度
max_depth = Math.max(max_depth, depth);
// 如果不存在对应深度的节点我们才插入
if (!rightmostValueAtDepth.containsKey(depth)) {
rightmostValueAtDepth.put(depth, node.val);
}
nodeStack.push(node.left);
nodeStack.push(node.right);
depthStack.push(depth + 1);
depthStack.push(depth + 1);
}
}
List rightView = new ArrayList();
for (int depth = 0; depth <= max_depth; depth++) {
rightView.add(rightmostValueAtDepth.get(depth));
}
return rightView;
}
}
题解思路：bfs
（7）222. 完全二叉树的节点个数思路：前序遍历，使用一个变量记录遍历的节点数；
class Solution {
int count;
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
dfs(root);
return count;
}
public void dfs(TreeNode root){
if(root == null){
return;
}
count++;
if(root.left != null){
dfs(root.left);
}
if(root.right != null){
dfs(root.right);
}
}
}
（8）236. 二叉树的最近公共祖先（错1）
思路：递归；对于递归问题：1.这个函数是干什么的；2.这个函数的参数变量是什么；3.得到递归的结果，该用来干什么；
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return root;
}
if(root == p || root == q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left != null && right != null){
return root;
}else if(left != null){
return left;
}else if(right != null){
return right;
}
return null;
}
}
（9）257. 二叉树的所有路径
思路：dfs遍历
class Solution {
List res = new ArrayList();
public List binaryTreePaths(TreeNode root) {
if(root == null){
return res;
}
String path = root.val+"";
if(root.left == null && root.right == null){
res.add(path);
return res;
}else{
if(root.left != null){
getPath(root.left, path);
}
if(root.right != null){
getPath(root.right, path);
}
}
return res;
}
public void getPath(TreeNode root, String path){
if(root == null){
return;
}
if(root.left == null && root.right == null){
res.add(path + "->"+root.val);
}else{
if(root.left != null){
getPath(root.left, path + "->"+root.val);
}
if(root.right != null){
getPath(root.right, path + "->"+root.val);
}
}
}
}
（10） 337. 打家劫舍 III（错1）
题解思路：树状动态规划，使用map存储节点的最优值。递归调用。
class Solution {
Map memo = new HashMap<>();
public int rob(TreeNode root) {
if(root == null){
return 0;
}
if(memo.containsKey(root)){
return memo.get(root);
}
int do_it = root.val
+ (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right))
+ (root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));
int not_do = rob(root.left) + rob(root.right);
int res = Math.max(do_it,not_do);
memo.put(root,res);
return res;
}
}
