常见算法题分类总结之二叉树(Binary-Tree)与经典问题
文章目录
- 先来了解一下树的基本知识(图文并茂)
- 再来看悉心挑选的试题
先来了解一下树的基本知识(图文并茂)
为了方便大家理解，树这部分采用PPT的形式给大家展现，相信大家会有比较形象深刻的记忆，其实树主要还是遍历，通过BFS或者DFS方式，具体实现用队列或者栈来完成，这些数据结构的基本操作是我们需要熟练于心的。
我们希望快速查找/插入/删除但是高度有时会达到0(n)，我们希望树是平衡的…下面介绍平衡二叉树
其中AVL树是最早被发明的自平衡二叉树，有时也被直接称为平衡二叉树
每次旋转用时=O(1)（仅修改相关节点的指针）
红黑树具体的插入删除及维护有点复杂，我以后会再写一篇博客专门讲这个内容
为什么要有红黑树：
我们为了更好地对数据进行增删改查操作，我们需要更好一点的数据结构，以提高我们的性能，而二叉搜索树看着不错，但是它的最坏情况下会变成一条线，如果我们可以使这个二叉搜索树一直处于一个平衡的状态，那我们就会达到O(log n)的运行时间。自平衡二叉树里面，举一个例子，红黑树，它通过定义的那几个性质，能够让自己一直保持着那种平衡的状态。
再来看悉心挑选的试题
路径之和
/** * 路径总和 * @author: William * @time:2022-03-23 */public class Num112 { public boolean hasPathSum(TreeNode root, int targetSum) { if(root == null) return false;//判断根节点 if(root.left == null && root.right == null && root.val == targetSum) return true; return hasPathSum(root.left, targetSum - root.val) ||hasPathSum(root.right, targetSum - root.val); }}翻转二叉树
/** * 翻转二叉树 * @author: William * @time:2022-03-23 */public class Num226 {public TreeNode invertTree1(TreeNode root) {if(root == null) return null;//下面三句就是将当前节点的左右子树交换TreeNode tmp = root.right;root.right = root.left;root.left = tmp;//递归交换当前节点的左子树，右子树invertTree1(root.left);invertTree1(root.right);//函数返回时就表示当前这个节点，以及它的左右子树都已经交换完了return root;}public TreeNode invertTree(TreeNode root) {if(root == null) return null;TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.left = right;root.right = left;return root; }public TreeNode invertTree2(TreeNode root) {if(root == null) return null;//将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()) {//每次都从队列中拿一个节点，并交换这个节点的左右子树TreeNode tmp = queue.poll();TreeNode left = tmp.left;tmp.left = tmp.right;tmp.right = left;//如果当前节点的左 右子树不为空，则放入队列等待后续处理if(tmp.left != null) queue.add(tmp.left);if(tmp.right != null) queue.add(tmp.right);}//返回处理完的根节点return root;}}监控二叉树(困难)
/** * 监控二叉树 - 困难 * @author: William * @time:2022-03-29 */public class Num968 {int count = 0;//简单易懂的后序遍历法public int minCameraCover(TreeNode root) {if(root == null) return 0;//空树不需要if(root.left == null && root.right == null)return 1;//只有根节点一个，只需要1//根据返回值，检查根节点是否被覆盖int val = helper(root);if(val == 0) count += 1;//没覆盖到要加一个return count;}/** * @return 0: 表示没有覆盖到 * 1: 覆盖到了，但是该节点没有摄像头 * 2: 覆盖到了，且该节点有摄像头 */public int helper(TreeNode root) {if(root == null) return 1;//空节点，当作覆盖到了//叶子节点，贪心的策略：使用其父节点放置摄像头，能覆盖更多的节点if(root.left == null && root.right == null) return 0;//后序遍历int left = helper(root.left);int right = helper(root.right);//子节点没有覆盖到的，必须在此处放置摄像头if(left == 0 || right == 0) {count++;return 2;}//子节点里有任意一个放置了摄像头，此处不需要重复放置，因为已经被覆盖if(left == 2 || right == 2) return 1;//子节点两个都被覆盖到了，没有放置摄像头，因此当前点没有覆盖return 0;}//需要维护的三种类型的状态：//状态 a：root 必须放置摄像头的情况下，覆盖整棵树需要的摄像头数目。//状态 b：覆盖整棵树需要的摄像头数目，无论 root 是否放置摄像头。//状态 c：覆盖两棵子树需要的摄像头数目，无论节点 root 本身是否被监控到//根据定义一定有a>=b>=c public int minCameraCover2(TreeNode root) {//官方int[] array = dfs(root);return array[1];}public int[] dfs(TreeNode root) {if(root == null) {return new int[] {Integer.MAX_VALUE / 2, 0, 0};}int[] L = dfs(root.left);int[] R = dfs(root.right);int[] array = new int[3];array[0] = L[2] + R[2] + 1;array[1] = Math.min(array[0], Math.min(L[0] + R[1], L[1] + R[0]));array[2] = Math.min(array[0], L[1] + R[1]);return array;}public int minCameraCover1(TreeNode root) {int[][] dp = new int[2][2];//前一个表示父节点是否安装，后一个表示当前节点getDp(root, dp);return Math.min(dp[0][0], dp[0][1]); }public void getDp(TreeNode root, int[][] dp) {if(root == null) {dp[0][0] = 0;dp[0][1] = 1111;dp[1][0] = 0;dp[1][1] = 1111;//安不上return;}if(root.left == null && root.right == null) {//叶子节点dp[0][0] = 1111;//这种情况监控不到dp[0][1] = 1;dp[1][0] = 0;//当前没安dp[1][1] = 1;return;}int [][] l = new int[2][2];int [][] r = new int[2][2];getDp(root.left, l);getDp(root.right, r);dp[0][0] = Math.min(Math.min(l[0][1] + r[0][0], l[0][0] + r[0][1]), l[0][1] + r[0][1]);dp[0][1] = Math.min(Math.min(l[1][0] + r[1][0], l[1][1] + r[1][1]), Math.min(l[1][1] + r[1][0], l[1][0] + r[1][1])) + 1;dp[1][0] = Math.min(dp[0][0], l[0][0] + r[0][0]);dp[1][1] = dp[0][1];}}树的子结构
/** * 树的子结构 * @author: William * @time:2022-03-29 */public class Num26 {//判断是子结构需要两步骤：//1.调用函数 isSubStructure(A, B) 遍历树A，先访问到节点A//2.调用函数 recur(A, B)public boolean isSubStructure(TreeNode A, TreeNode B) {return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)); }boolean recur(TreeNode A, TreeNode B) {//B为空，说明树B已匹配完成(越过叶子节点)if(B == null) return true;//A为空，说明已经越过树A叶子节点 返回失败if(A == null || A.val != B.val) return false;return recur(A.left, B.left) && recur(A.right, B.right);}}平衡二叉树
/** * 平衡二叉树 * @author: William * @time:2022-03-23 */public class Num110 {//开课吧的dfspublic boolean isBalanced4(TreeNode root) {return dfs(root) >= 0;}//求出当前以root为根节点的树的高度public int dfs(TreeNode root) {if(root == null) return 0;int left = dfs(root.left);int right = dfs(root.right);//下面返回-2都是因为不符合题意if(left < 0 || right < 0) return -2;//注意不能返回-1 不然不知道是因为root为空还是因为左右子树高度差大于1if(Math.abs(left - right) > 1) return -2;return Math.max(left, right) + 1;}//官方自底向上public boolean isBalanced2(TreeNode root) {return height(root) >= 0;}private int height(TreeNode root) {if(root == null) return 0;int leftHeight = height(root.left);int rightHeight = height(root.right);if(leftHeight == -1 || rightHeight == -1 ||Math.abs(leftHeight - rightHeight) > 1) {return -1;}else {return Math.max(leftHeight, rightHeight) + 1;}}//官方的优化public boolean isBalanced3(TreeNode root) { return balanced(root) != -1; } private int balanced(TreeNode node) { if (node == null) return 0; int leftHeight, rightHeight; if ((leftHeight = balanced(node.left)) == -1 || (rightHeight = balanced(node.right)) == -1 || Math.abs(leftHeight - rightHeight) > 1) return -1; return Math.max(leftHeight, rightHeight) + 1; }//从底至顶(提前阻断) 先序遍历 从底至顶返回子树最大高度//若不是平衡树则“剪枝”，直接向上返回public boolean isBalanced1(TreeNode root) {return recur(root) != -1; }private int recur(TreeNode root) {//递归终止条件，越过叶子节点时，返回高度0；另外-1也是终止条件if(root == null) return 0;int left = recur(root.left);if(left == -1) return -1;int right = recur(root.right);if(right == -1) return -1;//当root左右子树的高度差<2，则返回以root为根节点的子树的最大高度//>=2 就返回-1 代表此子树不是平衡树return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;}//从顶至底public boolean isBalanced(TreeNode root) { if (root == null) return true; return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } private int depth(TreeNode root) { if (root == null) return 0; return Math.max(depth(root.left), depth(root.right)) + 1; }}从前序与中序遍历序列构造二叉树
/** * 从前序与中序遍历序列构造二叉树 * @author: William * @time:2022-03-23 */public class Num105 {//大神普通版public TreeNode buildTree1(int[] preorder, int[] inorder) {return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);}private TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end) {//preorder 为空， 直接返回nullif(p_start == p_end) return null;int root_val = preorder[p_start];TreeNode root = new TreeNode(root_val);//在中序遍历中找到根节点的位置int i_root_index = 0;for(int i = i_start; i < i_end; i++) {if(root_val == inorder[i]) {i_root_index = i;break;}}int leftNum = i_root_index - i_start;//递归地构造左子树root.left = buildTreeHelper(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index); //递归的构造右子树 root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end); return root;} //大神HashMap版Map<Integer, Integer> map;public TreeNode buildTree2(int[] preorder, int[] inorder) {map = new HashMap<>();for(int i = 0; i < inorder.length; i++) {//map存的是中序遍历数组的每个元素的值和下标map.put(inorder[i], i);} return build(preorder, 0, preorder.length, inorder, 0, inorder.length); }private TreeNode build(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end) {if(p_start == p_end) return null;int root_val = preorder[p_start];//前序遍历拿到的根节点 可以在中序遍历中找到该节点TreeNode root = new TreeNode(root_val);int i_root_index = map.get(root_val);int leftNum = i_root_index - i_start;root.left = build(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index);root.right = build(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end);return root;}//天神下凡版！public TreeNode buildTree3(int[] preorder, int[] inorder) { return helper(preorder, inorder, (long)Integer.MAX_VALUE + 1);}//pre 保存当前要构造的树的根节点 从根节点开始递归的构造左子树和右子树//in 指向当前根节点可用数字的开头//对于当前pre有一个停止点stop//从in到stop表示要构造的树当前的数字范围int pre = 0, in = 0;private TreeNode helper(int[] preorder, int[] inorder, long stop) {//到达末尾返回nullif(pre == preorder.length) return null;//到达停止点返回null//当前停止点已经用了，in后移if(inorder[in] == stop) {in++;return null;}int root_val = preorder[pre++];TreeNode root = new TreeNode(root_val);//左子树的停止点是当前的根节点root.left = helper(preorder, inorder, root_val);//右子树的停止点是当前的根节点root.right = helper(preorder, inorder, stop);return root;}}剑指Offer 32 -Ⅱ 从上到下打印二叉树Ⅱ
/** * 剑指Offer 32 -Ⅱ 从上到下打印二叉树Ⅱ * @author: William * @time:2022-04-02 */public class Num32 {List<List<Integer>> res;//dfspublic List<List<Integer>> levelOrder(TreeNode root){res = new ArrayList<>();dfs(root, 0);return res;}public void dfs(TreeNode root, int level) {if(root == null) return;//这时候表示走到新的一层 需要new一个集合出来存储if(res.size() == level) res.add(new ArrayList<>());res.get(level).add(root.val);dfs(root.left, level + 1);dfs(root.right, level + 1);}//BFSpublic List<List<Integer>> levelOrder1(TreeNode root){Queue<TreeNode> queue = new LinkedList<>();res = new ArrayList<>();if(root != null) queue.add(root);while(!queue.isEmpty()) {//临时集合tmp 存储当前打印结果List<Integer> tmp = new ArrayList<>();for(int i = queue.size(); i > 0; i--) {TreeNode node = queue.poll();tmp.add(node.val);if(node.left != null) queue.add(node.left);if(node.right != null) queue.add(node.right);}res.add(tmp);}return res;}//自定义内部类 去bfsclass Data {TreeNode node;int level;public Data(TreeNode node, int level) {this.node = node;this.level = level;}}public List<List<Integer>> levelOrder2(TreeNode root){res = new ArrayList<>();if(root == null) return res;Queue<Data> queue = new ArrayDeque<>();queue.offer(new Data(root, 0));while(!queue.isEmpty()) {Data cur = queue.poll();int level = cur.level;TreeNode curNode = cur.node;if(res.size() == level) res.add(new ArrayList<>());res.get(level).add(curNode.val);if(curNode.left != null) queue.offer(new Data(curNode.left, level + 1));if(curNode.right != null) queue.offer(new Data(curNode.right, level + 1));}return res;}}二叉树的层序遍历Ⅱ
/** * 二叉树的层序遍历Ⅱ * @author: William * @time:2022-03-23 */public class Num107 {//dfs解法List<List<Integer>> res;public List<List<Integer>> levelOrderBottom1(TreeNode root) {res = new ArrayList<>();dfs(root, 0);Collections.reverse(res);return res;}public void dfs(TreeNode root, int level) {if(root == null) return;if(res.size() == level) res.add(new ArrayList<>());res.get(level).add(root.val);dfs(root.left, level + 1);dfs(root.right, level + 1);}public List<List<Integer>> levelOrderBottom(TreeNode root) {//参考102但是要记得翻转List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new ArrayDeque<>(); if (root != null) queue.add(root);//队列存结点 while (!queue.isEmpty()) { int n = queue.size();//直接用第一层就会有两个元素 List<Integer> level = new ArrayList<>(); for (int i = 0; i < n; i++) { TreeNode node = queue.poll();//队列出队 level.add(node.val);//加入到每层中 if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } res.add(0, level);//一直往头部插入 } return res; }}二叉树的锯齿形层序遍历
/** * 二叉树的锯齿形层序遍历 * @author: William * @time:2022-03-25 */public class Num103 {//bfs -- 顺序遍历+隔行反转public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new ArrayDeque<>(); boolean reverse = false; if (root != null) queue.add(root);//队列存结点 while (!queue.isEmpty()) { int n = queue.size();//直接用第一层就会有两个元素 List<Integer> level = new ArrayList<>(); for (int i = 0; i < n; i++) { TreeNode node = queue.poll();//队列出队 level.add(node.val);//加入到每层中 if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } if(reverse) Collections.reverse(level);//隔行反转 reverse = !reverse; res.add(level); } return res; }//dfs public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root != null) dfs(root, 0, res); return res; } private void dfs(TreeNode root, int level, List<List<Integer>> res) { if(root != null) { LinkedList<Integer> subList; if(level >= res.size()) { subList = new LinkedList<>(); res.add(subList); }else { subList = (LinkedList) res.get(level); } if(level % 2 == 0) { subList.add(root.val); }else { subList.addFirst(root.val); } dfs(root.left, level + 1, res); dfs(root.right, level + 1, res); } }}二叉树的前序遍历
/** * 二叉树的前序遍历 * @author: William * @time:2022-03-23 */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;}}public class Num144 {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();preorder(root, res);return res; }public void preorder(TreeNode root, List<Integer> res) {if(root == null) return;res.add(root.val);preorder(root.left, res);preorder(root.right, res);}}二叉树最大宽度
/** * 二叉树最大宽度 * @author: William * @time:2022-04-02 */public class Num662 {//DFSint ans;Map<Integer, Integer> left;public int widthOfBinaryTree1(TreeNode root) {ans = 0;left = new HashMap<>();dfs(root, 0, 0);return ans;}public void dfs(TreeNode root, int depth, int pos) {if(root == null) return;//添加最左侧的元素，当第一次走到某一层的时候，此时map里面是空，更新一次位置信息//若key对应的value为空，会将第二个参数的返回值存入并返回left.computeIfAbsent(depth, x-> pos);//计算当前结点跟最左侧结点位置的距离，并更新最大值ans = Math.max(ans, pos - left.get(depth) + 1);//计算左孩子的位置并记录所在层级，在遇到同层级的最左侧元素就可以参与运算得出距离dfs(root.left, depth + 1, 2 * pos);//计算右孩子的位置并记录所在层级dfs(root.right, depth + 1, 2 * pos + 1);}//自定义内部类 + bfsclass PNI{TreeNode root;int n;public PNI(TreeNode root, int n){this.root = root;this.n = n;}}public int widthOfBinaryTree(TreeNode root) {Queue<PNI> queue = new ArrayDeque<>();queue.offer(new PNI(root, 0));int ans = 0;while(!queue.isEmpty()) {int size = queue.size();int l = queue.peek().n;int r = 0;for(int i = 0; i < size; i++) {PNI tmp = queue.poll();r = tmp.n - l;if(tmp.root.left != null) {queue.offer(new PNI(tmp.root.left, r * 2));}if(tmp.root.right != null) {queue.offer(new PNI(tmp.root.right, r * 2 + 1));}}ans = ans > r + 1 ? ans : r + 1;}return ans; }}剑指Offer 54 二叉搜索树的第k大节点
/** * 剑指Offer 54 二叉搜索树的第k大节点 * @author: William * @time:2022-04-03 */public class Num54 {//二叉搜索树：左子树 < 根 < 右子树public int kthLargest(TreeNode root, int k) {int cnt = getCount(root.right);//说明这个数在右子树中if(cnt >= k) return kthLargest(root.right, k);//说明在根节点if(cnt + 1 == k) return root.val;//说明在左子树中return kthLargest(root.left, k - cnt - 1); }public int getCount(TreeNode root) {if(root == null) return 0;return 1 + getCount(root.left) + getCount(root.right);}//dfs方法int res, k;public int kthLargest1(TreeNode root, int k) {this.k = k;dfs(root);return res;}void dfs(TreeNode root) {if(root == null) return;dfs(root.right);if(k == 0) return;if(--k == 0) res = root.val;dfs(root.left);}}完全二叉树的节点个数
/** * 完全二叉树的节点个数 * @author: William * @time:2022-03-26 */public class Num222 {//完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，// 并且最下面一层的节点都集中在该层最左边的若干位置public int countNodes(TreeNode root) {//所有二叉树都适用的方法if(root == null) return 0;return countNodes(root.left) + countNodes(root.right) + 1; }//用到完全二叉树特性的解法public int countNodes1(TreeNode root) { if(root == null) return 0; int left = countLevel(root.left); int right = countLevel(root.right); if(left == right){//左子树一定是满二叉树 左子树节点总数为 2^left - 1 //加上当前这个root 正好是 2 ^ left 再对右子树进行递归统计 return countNodes1(root.right) + (1<<left); //上面位运算其实就是 (int)Math.pow(2, left) 的高端写法 }else{//不等于的情况说明最后一层不满，但是倒数第二层满了 //可直接得出右子树的节点数 同理为 2 ^ right return countNodes1(root.left) + (1<<right); } } private int countLevel(TreeNode root){ int level = 0; while(root != null){ level++; root = root.left; } return level; }}N叉树的前序遍历
/** * N叉树的前序遍历 * @author: William * @time:2022-03-23 */class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; }}/** * N叉树的前序遍历 * @author: William * @time:2022-03-23 */public class Num589 { public List<Integer> preorder(Node root) { List<Integer> res = new ArrayList<>(); helper(root, res); return res; } public void helper(Node root, List<Integer> res) { if (root == null) { return; } res.add(root.val); for (Node ch : root.children) { helper(ch, res); } }}
创作打卡挑战赛 
赢取流量/现金/CSDN周边激励大奖老人咖美文网