算法记录——树
二叉树
3.1二叉树的最大深度
思路：二叉树的最大深度 = 根节点的最大高度。因此本题可以转换为求二叉树的最大高度。
而求高度的时候应该采用后序遍历。遍历顺序为：左右中。每次遍历的节点按后序遍历顺序，先收集左右孩子的最大高度，再最后处理当前节点的最大高度！因此用后序遍历。
/**
* 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 int maxDepth(TreeNode root) {
//注意：这题虽然求的是最大的深度，但我们可以转换思路。求树的最大深度 = 根节点的最大高度！
if(root == null) return 0;
//当前节点左孩子的高度
int leftHeight = maxDepth(root.left);
//当前节点右孩子的高度
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight,rightHeight) + 1;//当前节点的最大高度就是左右孩子中更高的那个+1
}
}3.2 搜索二叉树的判断
思路：
首先我们知道二叉搜索树的性质：任何一个节点的左子树的所有节点的值都小于该节点的值，右子树的所有节点的值都大于该节点的值。
由这个性质我们可以知道，对于一个二叉搜索树，中序遍历这个树，得到的结构一定是升序的！
方法一：利用额外的集合，先中序遍历整个树，把每个值取到。再判断集合中是否为升序排序。
/**
* 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 static boolean isValidBST(TreeNode root) {
if(root.left == null && root.right == null) return true;
ArrayList<Integer> arr = new ArrayList();//用于存放每个节点值的集合
f(root,arr);
for (int i = 0; i < arr.size() - 1; i++) {
if (arr.get(i + 1) <= arr.get(i)) {
return false;
}
}
return true;
}
public static void f(TreeNode root, ArrayList arr) {//中序遍历
if (root == null) return;
f(root.left,arr);
arr.add(root.val);
f(root.right,arr);
}
}方法二：定义一个变量，用于保存每次要比较值的上一个值的大小。
/**
* 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 static boolean isValidBST(TreeNode root) {
if (root.left == null && root.right == null) return true;
Stack<TreeNode> stack = new Stack<>();
int preValue = Integer.MIN_VALUE;
while (!stack.isEmpty() || root != null) {
if (root != null) {//先一路把当前节点的左孩子全部遍历进栈
stack.push(root);
root = root.left;
} else {//总有一个时刻root跑到null，说明当前点没有左孩子
root = stack.pop();//root赋值为最后一个进栈的没有左孩子的节点
//这里刚遍历完当前节点的左孩子，如果在这里打印就是中序遍历
//System.out.print(root.val);
//所以我们在这里每次比较当前节点，和前一个要比较节点的大小，就相当于中序遍历
if (root.val > preValue || root.val == Integer.MIN_VALUE) {//说明当前节点满足搜索二叉树的性质
preValue = root.val;
} else {//否则不满足搜索二叉树，直接返回false
return false;
}
root = root.right;//遍历当前节点的右孩子
}
}
return true;
}
}3.3 判断完全二叉树
先说下性质：
满二叉树：在一颗二叉树中，如果每个结点都存在左子树和右子树，并且所有叶节点都在同一层上，这样的树为满二叉树。
完全二叉树：相同深度的满二叉树的所有结点（不包含叶子）在该树上都有相应的节点（包含叶子）与之对应且所有左子树先存在，才会存在右子树，然后才会存在下层子树的情况，这样的树为完全二叉树 。
可根据下图区分：
思路：层序遍历，根据完全二叉树的性质。
1.当有节点存在有右孩子没左孩子的时候，直接返回false
2.当遍历到第一个叶子节点时，要确保接下来每一个节点都是叶子节点！
/**
* 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 boolean isCompleteTree(TreeNode root) {
if (root == null) return true;
//创建一个队列用来做层序遍历
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
TreeNode l = null;//代表当前节点的左孩子
TreeNode r = null;//代表当前节点的右孩子
Boolean leaf = false;//一个开关，代表当前有没有遍历到叶子节点
while (!queue.isEmpty()) {
root = queue.poll();
l = root.left;
r = root.right;
if (
(leaf && (l != null || r != null))//前面已经存在叶子节点了，但当前节点不是叶子节点
||
(l == null && r != null)//有右无左直接返回false
) return false;
if (l == null || r == null) leaf = true;//如果当前节点是叶子节点
if (l != null) queue.add(l);
if (r != null) queue.add(r);
}
return true;
}
}3.4判断平衡二叉树
思路：
根据平衡二叉树的性质，判断当前节点下的树是不是平衡二叉树，只要做到一下几点判断：
1.左孩子要是平衡二叉树
2.右孩子要是平衡二叉树
3.左右孩子的高度差小于等于1
/**
* 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 boolean isBalanced(TreeNode root) {
if (root == null) return true;
boolean leftBalanced = isBalanced(root.left);//判断当前节点左子树是不是平衡二叉树
boolean rightBalanced = isBalanced(root.right);//判断当前节点右子树是不是平衡二叉树
int leftHeight = getHeight(root.left);//获取左子树高度
int rightHeight = getHeight(root.right);//获取右子树高度
//只有当左右子树都为平衡二叉树且左右子树高度差<=1时，当前点才是平衡二叉树
return leftBalanced && rightBalanced && (Math.abs(leftHeight - rightHeight) <= 1);
}
public static int getHeight(TreeNode root) {//获取当前节点的高度
if (root == null) return 0;
int leftHeight = getHeight(root.left);//获取当前节点左孩子的高度
int rightHeight = getHeight(root.right);//获取当前节点右孩子的高度
return Math.max(leftHeight, rightHeight) + 1;//当前点的高度 = 左右孩子中更高的高度+1
}
}3.5找二叉树中两个节点的最近公共祖先
方法一：比较麻烦，空间复杂度较高，但比较好理解。
思路：1.创建一个map集合，先遍历所有节点，把每个节点的父节点存放在当前集合中。
map<当前节点，当前节点的父节点>
2.创建一个set集合，遍历当前节点1的所有祖先节点，并全部放入set集合中。
3.遍历节点2的所有祖先节点。每次遍历判断set集合中有没有当前节点，如果有，当前节点就是二者的共同祖先。由于都是从下网上遍历，所以第一个共同祖先就是最近共同祖先！
注意：这里方法一只提供一种思路，但空间复杂度和时间复杂度都较高，不推荐。
方法一代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
HashMap<TreeNode, TreeNode> map = new HashMap<>();
map.put(root, root);//根节点的父节点就是自己
f(root, map);
HashSet<TreeNode> set = new HashSet<>();
set.add(p);
TreeNode cur = p;
while (cur != root) {//从p网上遍历其所有的祖先，把p每一个祖先都存放在set集合中
set.add(map.get(cur));
cur = map.get(cur);//当前节点赋值为其父节点
}
set.add(root);//根节点单独放入set集合
cur = q;
while (cur != root) {//遍历q的所有祖先，把q每个祖先都和p的祖先比较，当出现第一个相同节点，就是二者最近共同的祖先
if (set.contains(cur)) {
return cur;
}
cur = map.get(cur);//当前节点赋值为其父节点
}
return root;
}
/**
* 遍历树，把每个节点的父节点放入map集合中
*
* @param root 当前节点
* @param map 存放节点关系的集合
*/
public void f(TreeNode root, Map map) {
if (root == null) {
return;
}
map.put(root.left, root);
map.put(root.right, root);
f(root.left, map);
f(root.right, map);
}
}方法二：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//对于这个方法。如果某个子树下p、q都没有，它一定返回的就是空！
//遇到空就返回空，遇到p或q就返回p或q
if(root == null || root == p || root == q) return root;
TreeNode l = lowestCommonAncestor(root.left,p,q);//当前节点左子树的公共祖先
TreeNode r = lowestCommonAncestor(root.right,p,q);//当前节点右子树的公共祖先
if(l != null && r != null) return root;//如果当前节点的左右子树都有p或q。当前节点就是公共祖先
return l == null ? r : l;//如果左孩子为空就返回右孩子，如果右孩子也是空，那就也返回空！
}
}两个节点的分布无非就两种情况：
1.o1、o2中某一个是另一个的祖先。
2.o1、o2两个点分布在某一个公共祖先的两边。
情况一的图：
return l == null ? r : l;对于这种情况，A往左遍历，遍历到o1直接，就返回o1了。往右遍历，返回null。整体返回如果左不为空，就返回左，反之返回右。如果左右都为空，这返回右也就是返回空！
情况二的图：
if(l != null && r != null) return root;对于节点B。就是这种情况，左右两边返回值都不为空，返回的就是当前节点B。而对于B上面的节点，另外一边没有o1或o2，返回的一定是空。因此对于B和null，上面节点往上返回的还是B！
3.6前缀树
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
class TrieNode{
int pass;
int end;
HashMap<Character,TrieNode> nexts;
public TrieNode(){
pass = 0;
end = 0;
nexts = new HashMap<Character,TrieNode>();
}
}
public void insert(String word) {
if(word == null) return;
char[] chars = word.toCharArray();
root.pass++;
TrieNode node = root;
for(int i = 0; i < chars.length; i++){
if(node.nexts.get(chars[i]) == null){//当前节点第一次被加入
node.nexts.put(chars[i],new TrieNode());
}
node = node.nexts.get(chars[i]);
node.pass++;
}
node.end++;
}
public boolean search(String word) {
if(word == null) return true;
char[] chars = word.toCharArray();
TrieNode node = root;
for(int i = 0; i < chars.length; i++){
if(node.nexts.get(chars[i]) == null){//当前节点第一次被加入
return false;
}
node = node.nexts.get(chars[i]);
}
if(node.end > 0) return true;
return false;
}
public boolean startsWith(String prefix) {
if(prefix == null) return true;
char[] chars = prefix.toCharArray();
TrieNode node = root;
for(int i = 0; i < chars.length; i++){
if(node.nexts.get(chars[i]) == null){//当前节点第一次被加入
return false;
}
node = node.nexts.get(chars[i]);
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/3.7.树中任意两个点之间的最大距离
/**
* 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 int diameterOfBinaryTree(TreeNode root) {
ResInfo process = process(root);
return process.max - 1;
}
public ResInfo process(TreeNode root) {
if (root == null) return new ResInfo(0, 0);
//左右递归获取结果
ResInfo left = process(root.left);
ResInfo right = process(root.right);
int t = left.height + right.height + 1;
//当前点的最大距离为：
//如果当前根节点不参与：1.左孩子中最大距离 2.右孩子中最大距离
//当前点参与：3.左孩子最大高度 + 右孩子最大高度 + 1
//从以上三种情况中求最大值，就是以当前点为根的任意两点之间的最大距离max
int max = Math.max(Math.max(left.max, right.max), t);
//求当前点的最大高度：左右高度更高的 + 1
int height = Math.max(left.height, right.height) + 1;
return new ResInfo(max, height);
}
class ResInfo {
int max;//以当前点为根的任意两点之间的最大距离
int height;//当前点的最大高度
public ResInfo() {
}
public ResInfo(int max, int height) {
this.max = max;
this.height = height;
}
}
}3.8.节点与其子树之间的最大差值
/**
* 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 int maxAncestorDiff(TreeNode root) {
resType process = process(root);
return process.res;
}
public class resType {
int max;//其子树中的最小值
int min;//其子树中的最大值
int res;//最大差值
public resType() {
}
public resType(int max, int min, int res) {
this.max = max;
this.min = min;
this.res = res;
}
}
public resType process(TreeNode root) {
if (root == null) return new resType(Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
if (root.left == null && root.right == null) {//如果遍历到叶子节点
return new resType(root.val, root.val, 0);
}
//向左右子树要信息
resType leftRes = process(root.left);
resType rightRes = process(root.right);
int max = Math.max(leftRes.max, Math.max(rightRes.max, root.val));//找到左右子树中最大的值
int min = Math.min(leftRes.min, Math.min(rightRes.min, root.val));//找到左右子树中最小的值
//最大差值由可能由三部分组成
//左子树中的最大差值、右子树的最大差值
//以及，当前点与左右子树最大最小值绝对值之差
int res = Math.max(Math.abs(root.val - max), Math.abs(root.val - min));
res = Math.max(res, Math.max(leftRes.res, rightRes.res));
return new resType(max, min, res);
}
}3.9 二叉树的层平均值
这里注意的一点就是：每次循环队列长度就是该层的元素个数，这点需要注意一下。
/**
* 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<Double> averageOfLevels(TreeNode root) {
LinkedList<TreeNode> queue = new LinkedList<>();
ArrayList<Double> res = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()) {
//代表这一层元素的个数
int size = queue.size();
long sum = 0;
//遍历这一层
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
sum += node.val;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
res.add( ((double)sum / size));
}
return res;
}
}3.10.二叉树展开为链表
思路：
- 将左子树插入到右子树的地方
- 将原来的右子树接到左子树的最右边节点
- 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null
1
/ \
2 5
/ \ \
3 4 6
//将 1 的左子树插入到右子树的地方
1
\
2 5
/ \ \
3 4 6
//将原来的右子树接到左子树的最右边节点
1
\
2
/ \
3 4
\
5
\
6
//将 2 的左子树插入到右子树的地方
1
\
2
\
3 4
\
5
\
6
//将原来的右子树接到左子树的最右边节点
1
\
2
\
3
\
4
\
5
\
6
......public void flatten(TreeNode root) {
while (root != null) {
//左子树为 null，直接考虑下一个节点
if (root.left == null) {
root = root.right;
} else {
// 找左子树最右边的节点
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
//将原来的右子树接到左子树的最右边节点
pre.right = root.right;
// 将左子树插入到右子树的地方
root.right = root.left;
root.left = null;
// 考虑下一个节点
root = root.right;
}
}
}