二叉樹的定義及相關性質
注意：對于String來說，length()是一個方法诗祸，必須加括號
而對于數(shù)組來說屹培，length只是數(shù)組的父類Array從Object哪里繼承過來的屬性，所以是類的屬性沟绪，就不需要加括號
劍指offer 07 重建二叉樹
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int[] preorder;
HashMap<Integer, Integer> dic = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder; //將preorder 變成全局變量刮便， recur中可直接調用
//將inorder裝入HashMap中，方便后面查找root
for(int i=0; i<inorder.length; i++){
dic.put(inorder[i],i);
}
return recur(0,0,inorder.length - 1);
}
/**
* 利用inorder的最左和最右node分別在list中的第一和最后一個绽慈，不斷地迭代遍歷整個樹
* @param root_preIndx root在preorder中的index
* @param left_inIndx 整個樹的最左node在inorder中的index
* @param right_inIndx 整個樹的最右node在inorder中的index
* @return 當前樹的root
*/
public TreeNode recur (int root_preIndx, int left_inIndx, int right_inIndx){
//當最左node的index大于最右node的index恨旱， 即已經遍歷完
if(left_inIndx > right_inIndx){
return null;
}
TreeNode node = new TreeNode(preorder[root_preIndx]);
int root_inIndx = dic.get(preorder[root_preIndx]); //查詢root在inorder中的index
//node.left = 左子樹的root
node.left = recur(root_preIndx + 1, left_inIndx, root_inIndx - 1);
//求出左子樹在inorder中長度len_left辈毯，node.right在preorder中的index = root_preIndx + len_left
int len_left = root_inIndx - left_inIndx + 1;
node.right = recur(root_preIndx + len_left, root_inIndx + 1, right_inIndx);
return node;
}
}
劍指offer 26 樹的子結構
若樹B是樹A的子結構，樹A節(jié)點為M搜贤，樹B節(jié)點為N谆沃， 則
時間復雜度O(MN)
空間復雜度O(M)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null) return false;
if (treeCompare(A,B)) return true;
else return isSubStructure(A.left,B) || isSubStructure(A.right,B);
}
//開始對比子樹
public boolean treeCompare(TreeNode A, TreeNode B){
// 第一次是不會進來，因為上面調用條件是A,B同時不為null
// 之后再進來的前提則是A,B root 相同入客，對比child
if (B == null) return true;
//如果B == null 且 A != null 說明B 沒結束但A結束了 則肯定為false
if (A == null) return false;
if (A.val == B.val){
return treeCompare(A.left,B.left) && treeCompare(A.right,B.right);
}
else return false;
}
}
劍指offer 27 二叉樹的鏡像
時間復雜度O(N)
空間復雜度O(N)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
// 暫存左子樹
TreeNode temp = root.left;
// 遞歸
root.left = mirrorTree(root.right);
root.right = mirrorTree(temp);
//當無子節(jié)點時管毙，返回節(jié)點本身
return root;
}
}
劍指offer 28 對稱的二叉樹
時間復雜度O(N)
空間復雜度O(N)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return isEqual(mirrorTree(root.right),root.left);
}
public TreeNode mirrorTree(TreeNode root){
if(root == null) return null;
TreeNode temp = root.left;
root.left = mirrorTree(root.right);
root.right = mirrorTree(temp);
return root;
}
public boolean isEqual(TreeNode A, TreeNode B){
if(A == null && B == null) return true;
if(A == null && B != null) return false;
if(A != null && B == null) return false;
if(A.val != B.val) return false;
return isEqual(A.left,B.left) && isEqual(A.right,B.right);
}
}
劍指offer 32 從上到下打印二叉樹
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null) return new int[0];
// 注意：LinkedList,雙大寫
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> list = new ArrayList<>();
queue.add(root);
//注意：isEmpty()
while(!queue.isEmpty()){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
int[] ans = new int[list.size()];
// 括號之間用“;”隔開
for(int i = 0; i<list.size(); i++){
ans[i] = list.get(i);
}
return ans;
}
}
劍指offer 32-ii 從上到下打印二叉樹 ii
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
// 當root為null是，List也為null
if(root != null) queue.add(root);
while(!queue.isEmpty()){
List<Integer> temp = new ArrayList<>();
//注意：此時應從queue的size開始遞減,size為0時桌硫，queue為空
for(int i = queue.size(); i > 0; i--){
TreeNode node = queue.poll();
temp.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
ans.add(temp);
}
return ans;
}
}
劍指offer 32-iii 從上到下打印二叉樹 iii
基本思路： queue的存儲順序不變夭咬，根據(jù)奇偶行，在組temp時進行前插或順序排列铆隘，進而達到改變偶行讀取順序
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
int level = 1;
if(root != null) queue.add(root);
while(!queue.isEmpty()){
LinkedList<Integer> temp = new LinkedList<>();
int rem = level % 2;
if(rem == 0){
for(int i = queue.size(); i>0; i--){
TreeNode node = queue.poll();
// 偶行 從右至左
temp.addFirst(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
}
else{
for(int i = queue.size(); i>0; i--){
TreeNode node = queue.poll();
temp.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
}
ans.add(temp);
level++;
}
return ans;
}
}
劍指offer 33 二叉搜索樹的后序遍歷序列
基本思路：1.數(shù)列中最后一位是root
?????2.從左至右找出第一個比root大的node卓舵，位置記作temp（之后為右子樹，之前為左子樹）
?????3. temp之后若出現(xiàn)小于root膀钠，則為false
class Solution {
public boolean verifyPostorder(int[] postorder) {
// 數(shù)組 length不需要括號
return orderCheck(postorder, 0, postorder.length-1);
}
public boolean orderCheck(int[] postorder, int left, int right){
// 需要先判斷l(xiāng)eft 和 right 大小關系掏湾，否則會超出范圍
if(left >= right) return true;
int root = postorder[right];
int firstLarge = left;
// 找第一個大于root的節(jié)點
while(postorder[firstLarge] < root){
firstLarge++;
}
// 判斷之后是否都大于root
for(int temp = firstLarge; temp < right; temp++){
if(postorder[temp] < root) return false;
}
return orderCheck(postorder, left, firstLarge-1) && orderCheck(postorder, firstLarge, right-1);
}
}
劍指offer 34 二叉樹中和為某一值的路徑
經典回溯問題
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 必須寫在外面，否則方法內不能調用
public List<List<Integer>> ans = new ArrayList<>();
public LinkedList<Integer> list = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
helper(root,sum);
return ans;
}
//返回類型是void 空型 這里面如果return語句返回一個值的話會報錯肿嘲，
//如果就只是一個return;表示程序結束不繼續(xù)往下執(zhí)行融击。
public void helper(TreeNode root, int sum){
if(root == null) return;
sum -= root.val;
list.add(root.val);
if(root.left == null && root.right == null && sum == 0){
// 值得注意的是，記錄路徑時若直接執(zhí)行 ans.add(list) 則是將 list 對象加入了 ans 雳窟；
//后續(xù) list 改變時 ans 中的 list 對象也會隨之改變尊浪。
//正確做法：ans.add(new ArrayList(list)) 相當于復制了一個 list 并加入到 ans
ans.add(new ArrayList<>(list));
// 這里不加remove和return的目的是，接下來的子node都是null封救，下一步自動return
}
helper(root.left,sum);
helper(root.right,sum);
// remove目的是不改變 public list
list.removeLast();
}
}
劍指offer 55i 二叉樹的深度
第一個完全一次作對的題目 :) 加油拇涤，別放棄
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
劍指offer 55ii 平衡二叉樹
當左右平衡但子樹不平衡時
討論思考：如上圖所示，該題不僅要思考總樹是否平衡誉结，也要考慮子樹是否平衡鹅士。
不可以理所當然認為
getDeepth由于迭代，會在node 2時返回 -1惩坑，從而省去if(rightDeepth == -1 || leftDeepth == -1) return -1;事實上掉盅，在node 2時，確實會返回-1以舒，但此時函數(shù)并未完成怔接，即并未回歸到node 1，故
getDeepth(root)時,會返回Math.max(2,2)而非Math.max(3,3),所以最后仍不會得出正確答案稀轨。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
if(getDeepth(root) == -1) return false;
return true;
}
public int getDeepth(TreeNode root){
if(root == null) return 0;
int leftDeepth = getDeepth(root.left);
int rightDeepth = getDeepth(root.right);
// 計算root的左右兩邊是否高度差是否大于1
if(Math.abs(leftDeepth - rightDeepth) > 1) return -1;
// 計算 左右子樹 的高度差是否大于1
if(rightDeepth == -1 || leftDeepth == -1) return -1;
return Math.max(leftDeepth,rightDeepth) + 1;
}
}
劍指offer 37 序列化二叉樹
第一次挑戰(zhàn)困難的題，能夠讀懂并且寫明了岸军。 又進了一步奋刽，加油 :)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
TreeNode node;
// Encodes a tree to a single string.
// 雖然可以直接拼接字符串瓦侮，但是，在循環(huán)中佣谐，每次循環(huán)都會創(chuàng)建新的字符串對象肚吏，
//然后扔掉舊的字符串。這樣狭魂，絕大部分字符串都是臨時對象罚攀，不但浪費內存，還會影響GC效率雌澄。
public String serialize(TreeNode root) {
if(root == null) return "null";
Queue<TreeNode> queue = new LinkedList<>();
StringBuilder sb = new StringBuilder();
queue.add(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
// 1. 勿忘"null,"逗號 2. continue的作用：避免null上加null
if(node == null) {
sb.append("null,");
continue;
}
sb.append(node.val + ",");
queue.add(node.left);
queue.add(node.right);
}
// 一定要toString();因為return的type是string
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data == "null") return null;
String[] str = data.split(",");
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(str[0]));
queue.add(root);
for(int i = 1;i < str.length; i++){
/*
1
/ \
2 3
/ \
4 5
當node 2沒有child時斋泄，會被從queue中拿出然后 i += 1; 進行下一個node
*/
TreeNode parent = queue.poll();
if(!"null".equals(str[i])){
TreeNode left = new TreeNode(Integer.parseInt(str[i]));
parent.left = left;
queue.add(left);
}
i += 1;
if(!"null".equals(str[i])){
TreeNode right = new TreeNode(Integer.parseInt(str[i]));
parent.right = right;
queue.add(right);
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
劍指offer 54 二叉搜索書的第k大節(jié)點
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int k;
private int ans;
public int kthLargest(TreeNode root, int k) {
if(root == null) return 0;
this.k = k;
traversal(root);
return ans;
}
// 右 根 左
public void traversal(TreeNode root){
if(root == null) return;
traversal(root.right);
if(--this.k == 0) this.ans = root.val;
traversal(root.left);
}
}
