算法记录——树

 二叉树

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 {//否则不满足搜索二叉树，直接返回falsereturn 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或qif(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//从以上三种情况中求最大值，就是以当前点为根的任意两点之间的最大距离maxint max = Math.max(Math.max(left.max, right.max), t);//求当前点的最大高度：左右高度更高的 + 1int 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.二叉树展开为链表

思路：

1. 将左子树插入到右子树的地方
2. 将原来的右子树接到左子树的最右边节点
3. 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 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;}}
}