巨省网站,高端大气的网络公司名称,青县做网站,利川做网站二叉树 3.1二叉树的最大深度 思路#xff1a;二叉树的最大深度 根节点的最大高度。因此本题可以转换为求二叉树的最大高度。 而求高度的时候应该采用后序遍历。遍历顺序为#xff1a;左右中。每次遍历的节点按后序遍历顺序#xff0c;先收集左右孩子的最大高度#xff0c;… 二叉树 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;ArrayListInteger 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;StackTreeNode 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;//创建一个队列用来做层序遍历LinkedListTreeNode 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) {HashMapTreeNode, TreeNode map new HashMap();map.put(root, root);//根节点的父节点就是自己f(root, map);HashSetTreeNode 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;HashMapCharacter,TrieNode nexts;public TrieNode(){pass 0;end 0;nexts new HashMapCharacter,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 ListDouble averageOfLevels(TreeNode root) {LinkedListTreeNode queue new LinkedList();ArrayListDouble 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;}}
}
