递归，分治 有序数组选中间点m作为root，recursiely build subtrees m.left = build [l, m) m.right = build [m+1, r) public class Solution { public TreeNode sortedArrayToBST (int[] num) { if (num.length == 0) return null; return build(num, 0, num.length); } // build the BST for num[l:r) Tr...

DFS DFS时传递parentSum, childSum = parentSum*10 + child.val 时间O(n): 每个node访问一次 空间O(n): 因为是recursion，worst-case树是长条 所有node都在栈上 public class Solution { public int sumNumbers (TreeNode root) { return rec(root, 0); } public int rec(TreeNode root, int parentSum) { if (root == nul...

mergeSort, 在merge的时候count reversePairs 请看 https://www.youtube.com/watch?v=kvXPpFP9sXg 这哥们儿讲的很清楚 public class Solution { public int InversePairs(int [] array) { if (array.length < 2) return 0; int[] tmp = new int[array.length]; int ret = sortAndCount(0, array.length-1,...

JAVA 用双指针找倒数第n-1个节点 既然是删改链表，想都不想先把sentinal(stn)加到链表前方，这样边界问题处理轻松很多。 public class Solution { /** * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ public ListNode removeNthFromEnd (ListNode head, int n) { ListNode stn = new ListNode(0); ...

把element push到stack里从后往前加，没加一位记录进位。 import java.util.*; public class Solution { /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ public ListNode addInList (ListNode head1, ListNode head2) { Deque<ListNode> stack1 = new A...

JAVA - iterative import java.util.*; public class Solution { /** * * @param prices int整型一维数组 * @return int整型 */ public int maxProfit (int[] prices) { int min = Integer.MAX_VALUE; int maxProfit = 0; for (int p : prices) { maxProfit = Mat...

从个位数开始一位一位的加，记录进位(rem)。每一位的结果append到StringBuilder里。记得最后要把StringBuilder倒过来输出。 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算两个数之和 * @param s string字符串 表示第一个整数 * @param t string字符串 表示第二个整数 * @return string字符串 */ public...

JAVA - DP Solution, O(n) time, O(1) space 请输出不相邻最大子序列和 递归逻辑 f(0) = max(array[0], 0); f(1) = max(array[1], 0); f(2) = max(array[2], 0) + max(f(0)); f(3) = max(array[3], 0) + max(f(0), f(1)); f(4) = max(array[4], 0) + max(f(0), f(1), f(2)); ... ... f(x) = max(array[x], 0) + max(f(0), ... f(x-2))...

就双指针，但是要从大到小放，不然会overwrite还没用到的elem in A[]. public class Solution { public void merge(int A[], int m, int B[], int n) { int a = m, b = n; while (a + b > 0) { int id = a + b - 1; if (a == 0) { A[id] = B[--b]; } else if (b == 0) { A[id] = A[--a]; } e...

用一个global var记录LCA，然后dfs返回subtree里一共找到几个target。 如果两个都找到了 skip之后所有的backtrack(这个解法关键在于要确保LAC只被set一次) time O(n), space O(h), where h is height of tree. \ import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class S...

正常level-order traversal(因为比较好理解). 在visit的时候，用Deque去存值(因为Deque既是Queue也是Stack)。如果正向就当Queue(i.e. offer), 反向就当stack(i.e. push)。最后用Collection的copy constructor把Deque转化成ArrayList。 import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) { ...