# 0.4 想不到的思路

[48.Rotate Image](https://leetcode.com/problems/rotate-image/)

* 要求in-place
* clockwise的话就先reverse upside down, then swap symmetrically
* counter-clockwise的话就先reverse left to right, then swap symmetrically

117.Populating next right pointer each node

[124.Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)

* 因为treenode会包含负数
* 借着建立`public int maxSumSinglePath(TreeNode root, int[] max)`和计算每个node为tree的single path max sum
* 来获得maximum path sum, max\[0]

[173.Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/)

* 强记

[222.Count Complete Tree Nodes](https://leetcode.com/problems/count-complete-tree-nodes/)

* 如果一个tree是complete tree,那它的子树一定也是complete tree
* 所以先找leftPath,rightPath看是否相等，如果相等则说明是个perfect tree,直接2^h - 1

271.Encode and Decode String

* length + "#" + string,方法encode
* 不要用s.split("#")
* 节省空间的话也可以不用存储length,正确理解escape character
* '/'->'//', '#'->'/#'

[272.Closest BST Value II](https://leetcode.com/problems/closest-binary-search-tree-value-ii/)

* 求K个最近的value
* 用两个stack分别inorder存比target小的数，和比target大的数
* 这样两个stack的peek都是closest value

[358.Rearrange String K Distance Apart](https://leetcode.com/problems/rearrange-string-k-distance-apart/)

* 建两个map, int\[] count, int\[] valid,count存char-> cnt,valid存的是每个char从当前i开始可以出现的最小位置
* 思路就是每次取可以出现的char里cnt最大的char
* int selectValue( count, valid, start)// 返回的是要取的char在count里的index

[370.Range Addition](https://leetcode.com/problems/range-addition/)

* 每次只在startIndex上加val
* 在endIndex + 1处减val, 如果没越界的话
* 最后来个for-loop, prefix sum

[395.Longest Substring with At Least K Repeating Characters](https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/)

* 应该想到divide & conquer
* 先cnt所有char
* 然后顺序遍历a\~z,  如果cnt\[i] == 0, skip to next char. if cnt\[i] < k,说明最终返回的结果里肯定没有这个char,
* 所以就遍历string找到这个char,然后recursive call s.substring(0, i) 和substring(i + 1),在返回的left和right中返回大的

448.Find All numbers disappeared in an array

* mark by negating
