leetcode刷题笔记（7）

leetcode刷题笔记（7）

主题：二叉树

（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; }}