最大 BST 子樹(https://leetcode-cn.com/problems/largest-bst-subtree/)
法一：暴力枚舉
直觀的想法就是我枚舉每一個節(jié)點(diǎn)，去檢查這個節(jié)點(diǎn)為根的子樹是不是一棵二叉搜索樹绍坝，如果是的話就統(tǒng)計一下這個子樹的節(jié)點(diǎn)數(shù)并更新答案蚁阳，否則就繼續(xù)遞歸到左右子樹去找有沒有符合條件的二叉搜索樹宇驾。
時間復(fù)雜度：
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public static int largestBSTSubtree(TreeNode root) {
if(root == null){
return 0;
}
if(isBiSearchTree(root, -Integer.MAX_VALUE, Integer.MAX_VALUE)){
return count(root, 0);
}
return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
}
// 計算二叉樹的節(jié)點(diǎn)個數(shù)
public static int count(TreeNode root, int base){
if(root != null){
base++;
}
if(root.left != null){
base = count(root.left, base);
}
if(root.right != null){
base = count(root.right, base);
}
return base;
}
// 判斷二叉樹是否是搜索二叉樹
public static boolean isBiSearchTree(TreeNode root, int min, int max){
if(root == null){
return true;
}
if(root.val <= min || root.val >= max){
return false;
}
if(root.left == null && root.right == null){
return true;
}
if(root.left == null && root.right != null){
return isBiSearchTree(root.right, root.val, max);
}
if(root.left != null && root.right == null){
return isBiSearchTree(root.left, min, root.val);
}
if(root.left != null && root.right != null){
return isBiSearchTree(root.left, min, root.val) && isBiSearchTree(root.right, root.val, max);
}
return false;
}
法二：復(fù)用子樹信息
在法一判斷root節(jié)點(diǎn)是否是搜索二叉樹的時候秕硝，其實(shí)已經(jīng)將所有節(jié)點(diǎn)是否是搜索二叉樹計算了一遍暴浦，如果能夠復(fù)用這些子樹的信息警绩，就可以降低時間復(fù)雜度為O(N)崇败。
方法是從下往上搜索盅称，如果子樹不是搜索二叉樹肩祥，那么當(dāng)前樹必然也不是；如果子樹是搜索二叉樹缩膝，那么要判斷當(dāng)前節(jié)點(diǎn)值是否大于左子樹的最大值混狠，是否小于右子樹的最小值；
根據(jù)上面說的我們設(shè)計一個遞歸函數(shù) recursion(TreeNode node) 疾层，表示考慮當(dāng)前節(jié)點(diǎn)是不是一棵二叉搜索樹将饺，先遞歸左右子樹，拿到左右子樹是不是二叉搜索樹，以及相應(yīng)值的范圍予弧，再根據(jù)上文說的更新當(dāng)前的節(jié)點(diǎn)的信息即可刮吧。由于遞歸函數(shù)需要返回如下信息，則我們建一個結(jié)構(gòu)體存儲信息：
public static class Result{
boolean isBST; // 當(dāng)前樹是否是BST子樹
int size; // 當(dāng)前樹的最大BST子樹的節(jié)點(diǎn)個數(shù)
int max; // 當(dāng)前樹的最大節(jié)點(diǎn)值
int min; // 當(dāng)前樹的最小節(jié)點(diǎn)值
}
如果當(dāng)前節(jié)點(diǎn)是二叉搜索樹的話掖蛤，則需要更新當(dāng)前值的范圍：max即為右子樹的最大值杀捻，min即為左子樹的最小值；size為左右子樹的size之和再加1蚓庭；如果當(dāng)前節(jié)點(diǎn)不是二叉搜索樹的話致讥，那么之后此節(jié)點(diǎn)的父節(jié)點(diǎn)都不可能是二叉搜索樹，size就取左右子樹中大的那個器赞，將isBST設(shè)置為false垢袱，而max和min值已經(jīng)失去意義，不需要更新港柜；然后再遞歸回上一層更新其父親節(jié)點(diǎn)的信息请契，可以看出這是一個從下往上更新信息的過程。
public static int largestBSTSubtree(TreeNode root) {
if(root == null){
return 0;
}
Result result = recursion(root);
return result.size < 1 ? 1 : result.size;
}
public static Result recursion(TreeNode node){
if(node == null){
return null;
}
Result lRes = recursion(node.left);
Result rRes = recursion(node.right);
Result result = new Result();
boolean lValid = lRes == null || (lRes.isBST && node.val > lRes.max);
boolean rValid = rRes == null || (rRes.isBST && node.val < rRes.min);
// 當(dāng)前樹是BST
result.isBST = lValid && rValid;
if(lValid && rValid){
result.size = (lRes == null ? 0 : lRes.size) + (rRes == null ? 0 : rRes.size) + 1;
result.max = (rRes == null ? node.val : rRes.max);
result.min = (lRes == null ? node.val : lRes.min);
return result;
}
// 當(dāng)前樹不是BST, 那么只需要給size賦值, max和min已經(jīng)沒有意義
if(lRes != null && rRes != null){
result.size = lRes.size > rRes.size ? lRes.size : rRes.size;
}else if(lRes != null){
result.size = lRes.size;
}else if(rRes != null){
result.size = rRes.size;
}
return result;
}
二叉樹的右視圖(https://leetcode-cn.com/problems/binary-tree-right-side-view/)
給定一棵二叉樹潘懊，想象自己站在它的右側(cè)姚糊，按照從頂部到底部的順序，返回從右側(cè)所能看到的節(jié)點(diǎn)值授舟。
示例:
輸入: [1,2,3,null,5,null,4]
輸出: [1, 3, 4]
解釋:
技巧總結(jié)：
二叉樹的層序遍歷（廣度優(yōu)先遍歷）保留層數(shù)信息的兩種方式：
1）使用兩個隊(duì)列救恨，一個隊(duì)列保存value值，一個隊(duì)列同步保存對應(yīng)value值的層數(shù)释树；
2）只使用一個隊(duì)列肠槽，while循環(huán)中嵌套使用for循環(huán)，每次隊(duì)列出隊(duì)前讀取當(dāng)前隊(duì)列的size奢啥，然后for循環(huán)中進(jìn)行size次出隊(duì)列秸仙，剛好可以處理完一層的節(jié)點(diǎn)。
廣度優(yōu)先
因?yàn)橹恍枰Ａ裘繉又凶钣疫叺臄?shù)即可：
1）先入隊(duì)左兒子桩盲，再入隊(duì)右兒子寂纪，那么每層中最右邊的數(shù)，即每層中最后一個出隊(duì)列的
2）如何得到每層的數(shù)量：在遍歷之前讀取queue的size即可赌结；
public static List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root == null){
return ret;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (i == size - 1) {
ret.add(node.val);
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return ret;
}
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
或者利用額外一個隊(duì)列保存depth的信息捞蛋，每入隊(duì)或出隊(duì)一個node，對應(yīng)的depth queue就同樣出隊(duì)或者入隊(duì)一個depth信息柬姚；
class Solution {
public List<Integer> rightSideView(TreeNode root) {
Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
int max_depth = -1;
Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
Queue<Integer> depthQueue = new LinkedList<Integer>();
nodeQueue.add(root);
depthQueue.add(0);
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();
int depth = depthQueue.remove();
if (node != null) {
// 維護(hù)二叉樹的最大深度
max_depth = Math.max(max_depth, depth);
// 由于每一層最后一個訪問到的節(jié)點(diǎn)才是我們要的答案拟杉，因此不斷更新對應(yīng)深度的信息即可
rightmostValueAtDepth.put(depth, node.val);
nodeQueue.add(node.left);
nodeQueue.add(node.right);
depthQueue.add(depth+1);
depthQueue.add(depth+1);
}
}
List<Integer> rightView = new ArrayList<Integer>();
for (int depth = 0; depth <= max_depth; depth++) {
rightView.add(rightmostValueAtDepth.get(depth));
}
return rightView;
}
}
二叉樹的鋸齒形層次遍歷
層序遍歷二叉樹（廣度優(yōu)先遍歷）
此題需要知道層的信息，根據(jù)前面的總結(jié)量承，二叉樹的層數(shù)信息可以有兩種方式搬设，1）使用額外隊(duì)列同步保存level信息 2）使用while循環(huán)嵌套for循環(huán)穴店，每次while循環(huán)的開始讀取隊(duì)列的size
這里使用第2）種，因?yàn)榇a簡潔拿穴。
使用一個bool變量表示當(dāng)前層是奇數(shù)層還是偶數(shù)層泣洞，奇數(shù)層：list末尾添加；偶數(shù)層：list開頭添加默色；
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if(root == null){
return ret;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean isOddLevel = true;
while (!queue.isEmpty()){
int size = queue.size();
List<Integer> levelNums = new ArrayList<>();
for(int i=0; i<size; i++){
TreeNode currentNode = queue.poll();
if(isOddLevel){
levelNums.add(currentNode.val);
}else {
levelNums.add(0, currentNode.val);
}
if(currentNode.left != null){
queue.add(currentNode.left);
}
if(currentNode.right != null){
queue.add(currentNode.right);
}
}
ret.add(levelNums);
isOddLevel = !isOddLevel;
}
return ret;
}
從前序與中序遍歷序列構(gòu)造二叉樹
遞歸解法
private Map<Integer, Integer> indexMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) {
return null;
}
indexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
indexMap.put(inorder[i], i);
}
return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
public TreeNode buildTree(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart == preEnd) {
return new TreeNode(preorder[preStart]);
}
int rootValue = preorder[preStart];
TreeNode root = new TreeNode(rootValue);
int index = indexMap.get(rootValue);
int leftCount = index - inStart;
int rightCount = inEnd - index;
if (leftCount > 0) {
root.left = buildTree(preorder, inorder, preStart + 1, preStart + leftCount, inStart, index - 1);
}
if (rightCount > 0) {
root.right = buildTree(preorder, inorder, preStart + leftCount + 1, preEnd, index + 1, inEnd);
}
return root;
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
驗(yàn)證二叉搜索樹
遞歸
public boolean isValidBST(TreeNode root) {
return recursion(root, null, null);
}
public boolean recursion(TreeNode node, Integer greatThan, Integer lessThan){
if(node == null){
return true;
}
if(greatThan != null && node.val <= greatThan){
return false;
}
if(lessThan != null && node.val >= lessThan){
return false;
}
if(node.left != null && !recursion(node.left, greatThan, node.val)){
return false;
}
if(node.right != null && !recursion(node.right, node.val, lessThan)){
return false;
}
return true;
}
二叉樹展開為鏈表
遞歸
比較直觀的思路如下：可用遞歸實(shí)現(xiàn)
1）遞歸將左子樹展開為單鏈表L斜棚；
2）遞歸將右子樹展開為單鏈表R；
3）將R鏈接到L末尾，合并成一個單鏈表；
4）將root的左子樹置空置蜀，右子樹指向上面合并的單鏈表；
官方講解有很多更加簡潔的遞歸寫法义钉，但是理解起來比較費(fèi)力；這里還是用自己的遞歸寫法规肴，性能都是一樣的捶闸。
public void flatten(TreeNode root) {
if(root == null){
return;
}
// 將左子樹變成一個單鏈表
flatten(root.left);
// 將右子樹變成一個單鏈表
flatten(root.right);
// 右子樹為連接兩個單鏈表的結(jié)果
root.right = link(root.left, root.right);
// 左子樹置空
root.left = null;
}
public TreeNode link(TreeNode left, TreeNode right){
if(left == null){
return right;
}
TreeNode curr = left;
while (curr.right != null){
curr = curr.right;
}
curr.right = right;
return left;
}
迭代
1）將左子樹插入到右子樹的地方
2）將原來的右子樹接到左子樹的最右邊節(jié)點(diǎn)
3）考慮新的右子樹的根節(jié)點(diǎn)，一直重復(fù)上邊的過程拖刃，直到新的右子樹為 null
public void flatten(TreeNode root) {
while (root != null){
if(root.left == null){ // 左子樹為 null删壮，直接考慮下一個節(jié)點(diǎn)
root = root.right;
}else {
// 將左子樹接到右子樹的地方
TreeNode oriRight = root.right;
root.right = root.left;
root.left = null;
// 找到左子樹(現(xiàn)在右子樹)的最右邊節(jié)點(diǎn)
TreeNode ptr = root.right;
while (ptr.right != null){
ptr = ptr.right;
}
// 將原來的右子樹接到左子樹(現(xiàn)在右子樹)的最右邊節(jié)點(diǎn)
ptr.right = oriRight;
root = root.right;
}
}
}
重建二叉樹
1）先序遍歷確定根的位置，再用中序遍歷確定左右子樹的節(jié)點(diǎn)個數(shù)兑牡；
2）可先用HashMap存儲中序遍歷數(shù)組中各個數(shù)字的位置信息央碟；
3）遞歸的參數(shù)需要包含先序數(shù)組的范圍[preStart, End]，中序數(shù)組的范圍[inStart, inEnd]均函。
public static TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) {
return null;
}
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
indexMap.put(inorder[i], i);
}
return reversion(preorder, 0, preorder.length - 1, 0, inorder.length - 1, indexMap);
}
public static TreeNode reversion(int[] preorder, int preStart, int preEnd, int inStart, int inEnd, Map<Integer, Integer> indexMap) {
if (preStart == preEnd) {
TreeNode root = new TreeNode(preorder[preStart]);
return root;
}
int rootValue = preorder[preStart];
TreeNode root = new TreeNode(rootValue);
// 中序數(shù)組確定左右子樹的節(jié)點(diǎn)數(shù)目
int inMed = indexMap.get(rootValue);
int leftNodeCount = inMed - inStart;
if (leftNodeCount > 0) {
root.left = reversion(preorder, preStart + 1, preStart + leftNodeCount, inStart, inMed - 1, indexMap);
}
int rightNodeCount = inEnd - inMed;
if (rightNodeCount > 0) {
root.right = reversion(preorder, preStart + leftNodeCount + 1, preEnd, inMed + 1, inEnd, indexMap);
}
return root;
}
實(shí)現(xiàn) Trie (前綴樹)
Trie一般也叫字典樹亿虽。參考下圖：
這棵字典樹可以看成是如下單詞集合{banana, anana, nana, ana, na, a}構(gòu)成的樹。
1）構(gòu)造TrieNode
由上圖可以看出一個字典樹節(jié)點(diǎn)的成員變量應(yīng)該有：
- 所有兒子節(jié)點(diǎn)的鏈接：考慮到需要進(jìn)行對所有兒子節(jié)點(diǎn)進(jìn)行快速檢索苞也，并且每個節(jié)點(diǎn)最多有26個兒子節(jié)點(diǎn)洛勉，所以使用數(shù)組存儲，數(shù)組下標(biāo)對應(yīng)26個字母如迟，表示潛在的26個兒子收毫。
- 是否是兒子節(jié)點(diǎn)，可以設(shè)置一個boolean值（或者類似圖中所示殷勘，給每個節(jié)點(diǎn)添加一個額外的兒子節(jié)點(diǎn)此再，'$'符號，表示此節(jié)點(diǎn)是否是兒子節(jié)點(diǎn)）劳吠。這里使用前者引润。
節(jié)點(diǎn)的成員方法應(yīng)該有：
- 構(gòu)造方法
- 是否包含某個兒子節(jié)點(diǎn)
- 獲取任意一個兒子節(jié)點(diǎn)
- 是否是兒子節(jié)點(diǎn)巩趁；以及設(shè)置兒子節(jié)點(diǎn)痒玩；
2）實(shí)現(xiàn)Trie類的三種方法
Trie樹類似其他樹淳附，也有一個類成員變量root節(jié)點(diǎn)；
insert方法就是逐級添加兒子節(jié)點(diǎn)的過程蠢古，最后一個兒子節(jié)點(diǎn)設(shè)為End奴曙；
startwith方法就是逐級搜索兒子節(jié)點(diǎn)的過程；
search方法在startwith方法的基礎(chǔ)上草讶，判斷最后一個兒子節(jié)點(diǎn)是否是End即可洽糟。
public class Trie {
public class TrieNode{
TrieNode[] links;
boolean isEnd;
public TrieNode(){
links = new TrieNode[26];
}
public boolean containsChild(char c){
return links[c - 'a'] != null;
}
public TrieNode getChild(char c){
return links[c - 'a'];
}
public void setChild(char c, TrieNode node){
links[c - 'a'] = node;
}
public boolean isEnd(){
return isEnd;
}
public void setEnd(){
isEnd = true;
}
}
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode curr = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(!curr.containsChild(c)){
curr.setChild(c, new TrieNode());
}
curr = curr.getChild(c);
}
curr.setEnd();
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode curr = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(!curr.containsChild(c)){
return false;
}
curr = curr.getChild(c);
}
return curr.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode curr = root;
for(int i = 0; i < prefix.length(); i++){
char c = prefix.charAt(i);
if(!curr.containsChild(c)){
return false;
}
curr = curr.getChild(c);
}
return true;
}
}
另外一種構(gòu)造TrieNode的方法：
字母的value存為一個字段，而不是像上面的方法表示在數(shù)組的索引中堕战；
然后用HashMap保存所有兒子節(jié)點(diǎn)坤溃，實(shí)現(xiàn)O(1)的檢索效率；
是否是End節(jié)點(diǎn)嘱丢，通過在兒子節(jié)點(diǎn)中添加一個值為'$'的兒子即可薪介；
此種方法更容易被自然的想到。
public class Trie {
public class TrieNode{
Character value;
Map<Character, TrieNode> childMap;
public TrieNode(){}
public TrieNode(Character value){
this.value = value;
}
}
private static final Character END = '$';
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode curr = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(curr.childMap != null){
TrieNode child = curr.childMap.get(c);
if(child != null){
curr = child;
continue;
}
}
TrieNode newNode = new TrieNode(c);
curr.childMap = curr.childMap == null ? new HashMap<>() : curr.childMap;
curr.childMap.put(c, newNode);
curr = newNode;
}
// 插入結(jié)束符
curr.childMap = curr.childMap == null ? new HashMap<>() : curr.childMap;
curr.childMap.put(END, new TrieNode(END));
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode curr = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(curr != null && curr.childMap != null){
TrieNode node = curr.childMap.get(c);
if(node == null){
return false;
}
if(i == word.length() - 1 && node.childMap.containsKey(END)){
return true;
}
curr = node;
continue;
}
return false;
}
return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode curr = root;
for(int i = 0; i < prefix.length(); i++){
char c = prefix.charAt(i);
if(curr != null && curr.childMap != null){
TrieNode node = curr.childMap.get(c);
if(node == null){
return false;
}
curr = node;
continue;
}
return false;
}
return true;
}
}
路徑總和 II
public static List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> paths = new ArrayList<>();
if(root == null){
return paths;
}
List<Integer> path = new ArrayList<>();
path.add(root.val);
dfs(paths, path, sum, root.val, root);
return paths;
}
public static void dfs(List<List<Integer>> paths, List<Integer> path, int target, int sum, TreeNode root){
if(sum == target && root.left == null && root.right == null){
paths.add(new ArrayList<>(path));
return;
}
if(root.left != null){
sum += root.left.val;
path.add(root.left.val);
dfs(paths, path, target, sum, root.left);
sum -= root.left.val;
path.remove(path.size()-1);
}
if(root.right != null){
sum += root.right.val;
path.add(root.right.val);
dfs(paths, path, target, sum, root.right);
sum -= root.right.val;
path.remove(path.size()-1);
}
}
二叉樹中和為某一值的路徑
回溯
- 正向思維越驻，記錄當(dāng)前路徑的和汁政；注意作為參數(shù)的變量，在回溯調(diào)用之前和之后必須保持一致缀旁，所以在添加path到ans的時候记劈，將當(dāng)前節(jié)點(diǎn)的值加入的是剛new出來的rightAns中，而不是先加入path并巍，再付給rightAns目木。
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> ans = new ArrayList<>();
if(root == null){
return ans;
}
dfs(ans, new ArrayList<>(), root, 0, sum);
return ans;
}
public void dfs(List<List<Integer>> ans, List<Integer> path, TreeNode current, int pathSum, int sum){
if(pathSum + current.val == sum && current.left == null && current.right == null){
List<Integer> rightAns = new ArrayList<>(path);
rightAns.add(current.val);
ans.add(rightAns);
return;
}
if(current.left != null){
path.add(current.val);
dfs(ans, path, current.left, pathSum + current.val, sum);
path.remove(path.size()-1);
}
if(current.right != null){
path.add(current.val);
dfs(ans, path, current.right, pathSum + current.val, sum);
path.remove(path.size()-1);
}
}
- 逆向思維，記錄剩下的路徑值懊渡。
public void dfs(List<List<Integer>> ans, List<Integer> path, TreeNode current, int diff){
if(current == null){
return;
}
path.add(current.val);
diff -= current.val;
if(diff == 0 && current.left == null && current.right == null){
ans.add(new ArrayList<>(path));
}
dfs(ans, path, current.left, diff);
dfs(ans, path, current.right, diff);
path.remove(path.size()-1);
}
不同的二叉搜索樹 II
遞歸
- 注意遞歸函數(shù)的結(jié)束條件嘶窄，不能直接返回null，而是返回一個包含null元素的list距贷。因?yàn)榧词故侨~子節(jié)點(diǎn)也應(yīng)該有一個null的左子樹和一個null的右子樹柄冲。
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new ArrayList<>();
}
return generateTrees(1, n);
}
public List<TreeNode> generateTrees(int start, int end) {
List<TreeNode> trees = new ArrayList<>();
if (start > end) {
trees.add(null);
return trees;
}
for (int i = start; i <= end; i++) {
List<TreeNode> leftTrees = generateTrees(start, i - 1);
List<TreeNode> rightTrees = generateTrees(i + 1, end);
for (TreeNode leftTree : leftTrees) {
for (TreeNode rightTree : rightTrees) {
TreeNode root = new TreeNode(i);
root.left = leftTree;
root.right = rightTree;
trees.add(root);
}
}
}
return trees;
}
36. 二叉搜索樹與雙向鏈表
樹的旋轉(zhuǎn)
參考樹的旋轉(zhuǎn)操作
public Node treeToDoublyList(Node root) {
if(root == null){
return null;
}
while (root.right != null){
root = rotateWithRightChild(root);
}
Node maxNode = root;
while (root.left != null){
while (root.left.right != null){
root.left = rotateWithRightChild(root.left);
}
root = root.left;
}
Node minNode = root;
// 二叉樹搜索樹：每個節(jié)點(diǎn)只有左節(jié)點(diǎn)
maxNode.right = minNode;
Node curr = maxNode;
Node last = curr;
while (curr != minNode){
curr = curr.left;
curr.right = last;
last = curr;
}
curr.left = maxNode;
return curr;
}
public Node rotateWithRightChild(Node root){
Node ret = root.right;
Node rightChild = root.right;
root.right = null;
while (rightChild.left != null){
rightChild = rightChild.left;
}
rightChild.left = root;
return ret;
}
中序遍歷
class Solution {
Node pre, head;
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
void dfs(Node cur) {
if (cur == null) {
return;
}
dfs(cur.left);
if (pre != null) {
pre.right = cur;
} else {
head = cur;
}
cur.left = pre;
pre = cur;
dfs(cur.right);
}
}
刪除二叉搜索樹中的節(jié)點(diǎn)
遞歸
1）一般而言返回的仍然是root節(jié)點(diǎn)，所以遞歸的形式為：
root.right = deleteNode(root.right, key);
root.left = deleteNode(root.left, key);
2）deleteNode返回刪除對應(yīng)節(jié)點(diǎn)后的子樹的根忠蝗；這里的刪除现横，可以采用替換數(shù)字的方式；
兩種做法：使用右子樹的最小數(shù)代替阁最，或者使用左子樹的最大數(shù)代替戒祠；
注意替換數(shù)字后，還要遞歸刪除替換的最小數(shù)/最大數(shù)速种。
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if(root.val < key){
root.right = deleteNode(root.right, key);
}else if(root.val > key){
root.left = deleteNode(root.left, key);
}else {
TreeNode rightMin = root.right;
if(rightMin != null){
while (rightMin.left != null){
rightMin = rightMin.left;
}
root.val = rightMin.val;
root.right = deleteNode(root.right, rightMin.val); // 遞歸刪除替換的數(shù)
return root;
} else {
return root.left;
}
}
return root;
}
完全二叉樹的節(jié)點(diǎn)個數(shù)
二分法
1）用二分法判斷最后一行的最后一個節(jié)點(diǎn)的順序索引姜盈，最后一行的所有節(jié)點(diǎn)的索引必定在；
2）判斷最后一行的某個索引節(jié)點(diǎn)是否存在配阵，需要O(logN)復(fù)雜度馏颂；
總體復(fù)雜度為
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
int level = 0;
TreeNode ptr = root;
while (ptr.left != null){
level++;
ptr = ptr.left;
}
int min = 1;
int max = (int) Math.pow(2, level);
int lastIndex = 1;
while (min <= max){
int med = (min + max) / 2;
if(exist(root, med, level)){
lastIndex = med;
min = med + 1;
}else {
max = med - 1;
}
}
int count = (int) Math.pow(2, level) - 1 + lastIndex;
return count;
}
public boolean exist(TreeNode root, int index, int level){
TreeNode ptr = root;
int min = 1;
int max = (int) Math.pow(2, level);
for(int i=0; i<level; i++){
int med = (min + max) / 2;
if(index > med){
min = med + 1;
ptr = ptr.right;
}else {
ptr = ptr.left;
max = med;
}
}
return ptr != null;
}
二叉樹的完全性檢驗(yàn)
廣度優(yōu)先遍歷：層序遍歷
public boolean isCompleteTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
TreeNode prev = root;
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.remove();
if (prev == null && node != null)
return false;
if (node != null) {
queue.add(node.left);
queue.add(node.right);
}
prev = node;
}
return true;
}
另一種思路：按層遍歷節(jié)點(diǎn)示血，判斷每一個節(jié)點(diǎn)：
1）是否能有兒子節(jié)點(diǎn)
2）是否有左兒子卻沒右兒子
在遍歷每一層的節(jié)點(diǎn)時，需要根據(jù)下一層的兒子節(jié)點(diǎn)做判斷
public boolean isCompleteTree(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 0;
boolean couldHasChild = true;
while (!queue.isEmpty()) {
int size = queue.size();
if (size < (int) Math.pow(2, level++)) {
couldHasChild = false;
}
for (int i = 0; i < size; i++) {
TreeNode current = queue.poll();
if (current.left == null && current.right != null) {
return false;
}
if (!couldHasChild && hasChild(current)) {
return false;
}
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
if(current.left == null || current.right == null){
couldHasChild = false;
}
}
}
return true;
}
public boolean hasChild(TreeNode node) {
return node.left != null || node.right != null;
}
序列化和反序列化二叉搜索樹
后續(xù)遍歷
public class Codec {
public String serialize(TreeNode root) {
StringBuilder stringBuilder = new StringBuilder();
postReverse(root, stringBuilder);
return stringBuilder.toString().trim();
}
public String postReverse(TreeNode node, StringBuilder sb) {
if (node == null) {
return sb.toString();
}
postReverse(node.left, sb);
postReverse(node.right, sb);
sb.append(node.val);
sb.append(" ");
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if("".equalsIgnoreCase(data)){
return null;
}
String[] strings = data.split("\\s+");
int[] nums = new int[strings.length];
for (int i = 0; i < strings.length; i++) {
nums[i] = Integer.parseInt(strings[i]);
}
return recover(nums, 0, nums.length - 1);
}
public TreeNode recover(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int value = nums[right];
TreeNode node = new TreeNode(value);
int med = left;
while (med < right && nums[med] < value) {
med++;
}
node.left = recover(nums, left, med - 1);
node.right = recover(nums, med, right - 1);
return node;
}
}
- 對于上述尋找左子樹和右子樹的分界點(diǎn)救拉，這一步驟其實(shí)沒有必要难审，后續(xù)遍歷為“左，右亿絮，根”告喊，取完末尾元素構(gòu)建根節(jié)點(diǎn)之后，之前的相鄰元素就是右子樹派昧，緊接著構(gòu)建右子樹黔姜，每構(gòu)建一個節(jié)點(diǎn)，就remove掉蒂萎，等到右子樹構(gòu)建完地淀，自然就輪到左子樹的節(jié)點(diǎn)了，只要給一個子樹的取值范圍即可岖是。
public TreeNode deserialize(String data) {
if("".equalsIgnoreCase(data)){
return null;
}
String[] strings = data.split("\\s+");
ArrayList<Integer> nums = new ArrayList<>();
for (int i = 0; i < strings.length; i++) {
nums.add(Integer.parseInt(strings[i]));
}
return recover(nums, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public TreeNode recover(ArrayList<Integer> nums , int min, int max) {
if (nums.size() == 0) {
return null;
}
int value = nums.get(nums.size()-1); // 取根節(jié)點(diǎn)
if(value < min || value > max){ // 判斷節(jié)點(diǎn)是不是在對應(yīng)的范圍內(nèi)
return null;
}
nums.remove(nums.size()-1); // 移除節(jié)點(diǎn)
TreeNode node = new TreeNode(value);
node.right = recover(nums, value, max); // 構(gòu)建右子樹必須在前
node.left = recover(nums, min, value); // 構(gòu)建左子樹必須在后
return node;
}
二叉搜索樹中第K小的元素
遞歸-中序遍歷
public ArrayList<Integer> inorder(TreeNode root, ArrayList<Integer> arr) {
if (root == null) return arr;
inorder(root.left, arr);
arr.add(root.val);
inorder(root.right, arr);
return arr;
}
public int kthSmallest(TreeNode root, int k) {
ArrayList<Integer> nums = inorder(root, new ArrayList<Integer>());
return nums.get(k - 1);
}
迭代-中序遍歷
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()){
while (current != null){
stack.push(current);
current = current.left;
}
current = stack.pop();
if(k == 1){
return current.val;
}
k--;
current = current.right;
}
return -1;
}
從中序與后序遍歷序列構(gòu)造二叉樹
遞歸
- 注意使用map存儲inorder的數(shù)值和下標(biāo)的映射關(guān)系
// 左 根 右
// 左 右 根
private Map<Integer, Integer> index;
public TreeNode buildTree(int[] inorder, int[] postorder) {
index = new HashMap<>();
int n = inorder.length;
for (int i = 0; i < n; i++) {
index.put(inorder[i], i);
}
return buildTree(inorder, 0, n - 1, postorder, 0, n - 1);
}
public TreeNode buildTree(int[] inorder, int left, int right, int[] postorder, int L, int R) {
if (left > right || L > R) {
return null;
}
TreeNode root = new TreeNode(postorder[R]);
int med = index.get(postorder[R]);
// right - left = R - L
root.left = buildTree(inorder, left, med - 1, postorder, L, L + med - 1 - left);
root.right = buildTree(inorder, med + 1, right, postorder, R - right + med, R - 1);
return root;
}
單詞的壓縮編碼
存儲單詞后綴
public int minimumLengthEncoding(String[] words) {
Set<String> good = new HashSet(Arrays.asList(words));
for (String word: words) {
for (int k = 1; k < word.length(); ++k)
good.remove(word.substring(k));
}
int ans = 0;
for (String word: good)
ans += word.length() + 1;
return ans;
}
字典樹
去找到是否不同的單詞具有相同的后綴帮毁，我們可以將其反序之后插入字典樹中。例如豺撑，我們有 "time" 和 "me"烈疚，可以將 "emit" 和 "em" 插入字典樹中。
- 反序加入單詞到trie中聪轿，即add方法
- 字典樹節(jié)點(diǎn)：TrieNode類爷肝，維護(hù)所有兒子節(jié)點(diǎn)（數(shù)組、HashMap）陆错，及是否是葉子節(jié)點(diǎn)
- 返回所有葉子節(jié)點(diǎn)的"高度+1"的和灯抛，即getCount方法
public int minimumLengthEncoding(String[] words) {
Trie trie = new Trie();
for(String word : words){
trie.add(word);
}
int ans = trie.getCount();
return ans;
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode(true);
}
public void add(String word) {
TrieNode ptr = root;
for (int i = word.length() - 1; i >= 0; i--) {
int index = word.charAt(i) - 'a';
if (ptr.child[index] == null) {
ptr.child[index] = new TrieNode(true); // 添加孩子
ptr.isLeaf = false;
}
ptr = ptr.child[index];
}
}
public int getCount(){
return getCount(root, 0);
}
public int getCount(TrieNode node, int height) {
if(node == null){
return 0;
}
if (node.isLeaf) {
return height + 1;
}
int total = 0;
for (TrieNode trieNode : node.child) {
total += getCount(trieNode, height + 1);
}
return total;
}
}
class TrieNode {
TrieNode[] child = new TrieNode[26];
boolean isLeaf;
public TrieNode(boolean isLeaf) {
this.isLeaf = isLeaf;
}
}
優(yōu)化
上面的代碼中，獲取所有葉子節(jié)點(diǎn)時音瓷，通過從遍歷字典樹得到对嚼，其實(shí)在加入word的時候，可以用一個HashMap將每個word對應(yīng)的末尾節(jié)點(diǎn)存儲下來绳慎，這樣通過遍歷HashMap纵竖，就可以得到所有的葉子節(jié)點(diǎn)，同時對應(yīng)word的length就是葉子節(jié)點(diǎn)的高度杏愤。
public int minimumLengthEncoding(String[] words) {
Trie trie = new Trie();
for(String word : words){
trie.add(word);
}
int ans = trie.getCount();
return ans;
}
class Trie {
TrieNode root;
HashMap<TrieNode, String> leafWordMap;
public Trie() {
root = new TrieNode(true);
leafWordMap = new HashMap<>();
}
public void add(String word) {
TrieNode ptr = root;
for (int i = word.length() - 1; i >= 0; i--) {
int index = word.charAt(i) - 'a';
if (ptr.child[index] == null) {
ptr.child[index] = new TrieNode(true); // 添加孩子
ptr.isLeaf = false;
}
ptr = ptr.child[index];
}
leafWordMap.put(ptr, word); // 潛在的葉子節(jié)點(diǎn)
}
public int getCount(){
int count = 0;
for(TrieNode trieNode : leafWordMap.keySet()){
if(trieNode.isLeaf){
count += leafWordMap.get(trieNode).length() + 1;
}
}
return count;
}
}
class TrieNode {
TrieNode[] child = new TrieNode[26];
boolean isLeaf;
public TrieNode(boolean isLeaf) {
this.isLeaf = isLeaf;
}
}
二叉樹中所有距離為 K 的結(jié)點(diǎn)
遞歸
public class Solution {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
private List<Integer> ans;
private TreeNode target;
private int K;
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
ans = new LinkedList();
this.target = target;
this.K = K;
dfs(root);
return ans;
}
// 返回當(dāng)前節(jié)點(diǎn)與target節(jié)點(diǎn)的之間的路徑上的節(jié)點(diǎn)數(shù)(即當(dāng)前節(jié)點(diǎn)與target節(jié)點(diǎn)之間的距離+1); 如果路徑不存在, 返回-1;
public int dfs(TreeNode node) {
if (node == null)
return -1;
else if (node == target) {
subtree_add(node, 0);
return 1;
} else {
int L = dfs(node.left);
int R = dfs(node.right);
if (L != -1) {
if (L == K) {
ans.add(node.val);
}
subtree_add(node.right, L + 1);
return L + 1;
} else if (R != -1) {
if (R == K) {
ans.add(node.val);
}
subtree_add(node.left, R + 1);
return R + 1;
} else {
return -1;
}
}
}
// 添加node節(jié)點(diǎn)以下與node節(jié)點(diǎn)距離為K-dist的節(jié)點(diǎn)
public void subtree_add(TreeNode node, int dist) {
if (node == null || dist > K)
return;
if (dist == K)
ans.add(node.val);
else {
subtree_add(node.left, dist + 1);
subtree_add(node.right, dist + 1);
}
}
}
添加父指針+雙隊(duì)列
- 將每個節(jié)點(diǎn)的父節(jié)點(diǎn)存儲在HashMap中
- 從target節(jié)點(diǎn)開始遍歷靡砌，將節(jié)點(diǎn)入隊(duì)列的同時，將對應(yīng)的distance也入隊(duì)列珊楼。節(jié)點(diǎn)隊(duì)列和距離隊(duì)列必須同步操作通殃，同時出棧和入棧，即可得到節(jié)點(diǎn)的同時得到其對應(yīng)的距離厕宗。當(dāng)節(jié)點(diǎn)的距離為0時画舌，是我們需要的答案堕担；對于每個節(jié)點(diǎn)判斷完畢之后，加入其父節(jié)點(diǎn)骗炉，左節(jié)點(diǎn)和右節(jié)點(diǎn)，同時其距離減1蛇受。
- 用HashSet保存訪問過的節(jié)點(diǎn)句葵；
public class Solution {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
private Map<TreeNode, TreeNode> parentMap;
private HashSet<TreeNode> visited;
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
List<Integer> ans = new ArrayList<>();
if (K == 0) {
ans.add(target.val);
return ans;
}
parentMap = new HashMap();
visited = new HashSet<>();
// 獲取所有節(jié)點(diǎn)的父節(jié)點(diǎn)
dfs(root, null);
// 從target節(jié)點(diǎn)開始遍歷
Queue<TreeNode> nodeQueue = new LinkedList();
Queue<Integer> distQueue = new LinkedList<>();
nodeQueue.add(target);
distQueue.add(K);
while (!nodeQueue.isEmpty()) {
TreeNode currentNode = nodeQueue.poll();
int dist = distQueue.poll();
if (!visited.contains(currentNode)) {
visited.add(currentNode);
if (dist == 0) {
ans.add(currentNode.val);
} else {
// 添加父節(jié)點(diǎn)
TreeNode parent = parentMap.get(currentNode);
if (parent != null && !visited.contains(parent)) {
nodeQueue.add(parent);
distQueue.add(dist - 1);
}
// 添加左節(jié)點(diǎn)或者右節(jié)點(diǎn)
if (currentNode.left != null && !visited.contains(currentNode.left)) {
nodeQueue.add(currentNode.left);
distQueue.add(dist - 1);
}
if (currentNode.right != null && !visited.contains(currentNode.right)) {
nodeQueue.add(currentNode.right);
distQueue.add(dist - 1);
}
}
}
}
return ans;
}
public void dfs(TreeNode node, TreeNode par) {
if (node != null) {
parentMap.put(node, par);
dfs(node.left, node);
dfs(node.right, node);
}
}
}
