二叉树的定义及相关性质
注意：对于String来说，length()是一个方法，必须加括号
而对于数组来说，length只是数组的父类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节点为M，树B节点为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);
//当无子节点时，返回节点本身
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的存储顺序不变，根据奇偶行，在组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.数列中最后一位是root
2.从左至右找出第一个比root大的node，位置记作temp（之后为右子树，之前为左子树）
3. temp之后若出现小于root，则为false
class Solution {
public boolean verifyPostorder(int[] postorder) {
// 数组 length不需要括号
return orderCheck(postorder, 0, postorder.length-1);
}
public boolean orderCheck(int[] postorder, int left, int right){
// 需要先判断left 和 right 大小关系，否则会超出范围
if(left >= right) return true;
int root = postorder[right];
int firstLarge = left;
// 找第一个大于root的节点
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;表示程序结束不继续往下执行。
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){
// 值得注意的是，记录路径时若直接执行 ans.add(list) 则是将 list 对象加入了 ans ；
//后续 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，但此时函数并未完成，即并未回归到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 序列化二叉树
第一次挑战困难的题，能够读懂并且写明了。 又进了一步，加油 :)
/**
* 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.
// 虽然可以直接拼接字符串，但是，在循环中，每次循环都会创建新的字符串对象，
//然后扔掉旧的字符串。这样，绝大部分字符串都是临时对象，不但浪费内存，还会影响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大节点
/**
* 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);
}
}
