当前位置：首页 > news >正文

二叉树高频题目-上-不含树型dp

news 来源：原创 2024/9/20 0:02:08

二叉树高频题目-上-不含树型dp

题目1 : 二叉树的层序遍历

测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/
思路
- 自己使用数组实现队列, 在队列中进行广度优先遍历
- 先将根结点进队, 如果队列里还有东西, 按照队列大小进行循环, 让队列里的结点进入本层的链表中, 如果正在处理的结点有子节点, 就让左右节点分别进入队列, 待每层的循环结束后, 将该层的列表装入总列表中
- 待队列里没有节点, 返回

代码O(n)

// 如果测试数据量变大了就修改这个值public static int MAXN = 2001;// 没有数据类型的初始化,别忘了赋值public static TreeNode[] queue = new TreeNode[MAXN];public static int l, r;// l: 拿数拿l位置的数,l++ r: 放数放r位置的数, r++// 提交时把方法名改为levelOrder，此方法为每次处理一层的优化bfs，此题推荐public static List<List<Integer>> levelOrder2(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();// 记录所有层的结点if (root != null) {// 如果二叉树不为空l = r = 0;// 逻辑清空queue[r++] = root;// 先把根结点进队列while (l < r) { // 队列里还有东西int size = r - l;// 队列大小ArrayList<Integer> list = new ArrayList<Integer>();// 用于记录该层结点for (int i = 0; i < size; i++) {// 如下行为重复size遍TreeNode cur = queue[l++];// 弹出一个节点list.add(cur.val);// 把它放在本层的链表里去if (cur.left != null) {// 有左加左queue[r++] = cur.left;}if (cur.right != null) {// 有右加右queue[r++] = cur.right;}}ans.add(list);// ans接收这一层的链表}}return ans;}

题目2 : 二叉树的锯齿形层序遍历

测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
思路
- 先判断根节点是否为空, 为空直接返回ans
- 不为空, 加入根结点
- 先收集结点
  - reverse == false, 左 -> 右， l…r-1, 收集size个
  - reverse == true, 右 -> 左， r-1…l, 收集size个
  - 左 -> 右, i = i + 1
  - 右 -> 左, i = i - 1
- 后进行广度优先遍历
- 搜集该层并置reverse = !reverse
- 返回ans

代码O(n)

public class Code02_ZigzagLevelOrderTraversal {// 不提交这个类public static class TreeNode {public int val;public TreeNode left;public TreeNode right;}// 提交以下的方法// 用每次处理一层的优化bfs就非常容易实现// 如果测试数据量变大了就修改这个值public static int MAXN = 2001;public static TreeNode[] queue = new TreeNode[MAXN];public static int l, r;public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();if (root != null) {l = r = 0;queue[r++] = root;// false 代表从左往右// true 代表从右往左boolean reverse = false; while (l < r) {int size = r - l;ArrayList<Integer> list = new ArrayList<Integer>();// 1. 收集结点// reverse == false, 左 -> 右， l....r-1, 收集size个// reverse == true,  右 -> 左， r-1....l, 收集size个// 左 -> 右, i = i + 1// 右 -> 左, i = i - 1for (int i = reverse ? r - 1 : l, j = reverse ? -1 : 1, k = 0; k < size; i += j, k++) {TreeNode cur = queue[i];list.add(cur.val);// 加的是.val}// 2. 广度优先遍历for (int i = 0; i < size; i++) {TreeNode cur = queue[l++];if (cur.left != null) {queue[r++] = cur.left;}if (cur.right != null) {queue[r++] = cur.right;}}ans.add(list);// 收集该层reverse = !reverse;// 反转}}return ans;}}

题目3 : 二叉树的最大特殊宽度

测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/
思路
- 将每一个节点进行编号(此处从1开始), nq为节点队列, iq为id队列
- 每次BFS结点入队时编号也要入队
- 当每层节点入队完成, 最大宽度: 最右结点编号 - 最左结点编号 + 1
- 选取最大宽度

代码O(n)

// 用每次处理一层的优化bfs就非常容易实现// 如果测试数据量变大了就修改这个值public static int MAXN = 3001;public static TreeNode[] nq = new TreeNode[MAXN];// 结点队列public static int[] iq = new int[MAXN];// id队列public static int l, r;public static int widthOfBinaryTree(TreeNode root) {l = r = 0;// 初始化结点队列int ans = 1;// 根// 同步放根nq[r] = root;// nq里面放rootiq[r++] = 1;// iq里面放1while (l < r) {// 结点队列有值int size = r - l;// 左	...	右// l	...	r-1ans = Math.max(ans, iq[r - 1] - iq[l] + 1);// 取最大的宽度for (int i = 0; i < size; i++) {// 一次处理一层的BFS// 弹出TreeNode node = nq[l];int id = iq[l++];// 有左放左if (node.left != null) {nq[r] = node.left;iq[r++] = id * 2;// 注意自己的编号}// 有右放右if (node.right != null) {nq[r] = node.right;iq[r++] = id * 2 + 1;// 注意自己的编号}}}//whilereturn ans;}

题目4 : 求二叉树的最大深度、求二叉树的最小深度

1. 最大深度

测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/
思路
- 递归
- 当前结点是否为空?
  - 为空, 返回深度: 0
  - 不为空, 返回左右子树最大深度 + 1(本层所占的深度)

代码O(n)

public static int maxDepth(TreeNode root) {return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}

2. 最小深度

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

如下图: a -> b -> c 为有效路径 a -> b -> null 为无效路径

(有叶子结点一定要走到叶子结点)

测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/

思路

递归
当前的树是空树. 最小深度为0
当前树只有根结点, 最小深度为1
当前树不是以上两种情况
- 设置两个变量标识最右最小深度, 初始化为整数最大值
- 若左子树不为空, 递归计算左子树的最小深度
- 若右子树不为空, 递归计算右子树的最小深度
- 返回左右子树的最小深度+1(当前层所占深度)

代码O(n)

	public int minDepth(TreeNode root) {// 从根数到某个叶子结点if (root == null) {// 当前的树是空树return 0;}if (root.left == null && root.right == null) {// 当前root是叶节点return 1;}int ldeep = Integer.MAX_VALUE;int rdeep = Integer.MAX_VALUE;// 只能调有节点的一边, 否则会被干扰, 计算出一个不符合要求的最小深度if (root.left != null) {ldeep = minDepth(root.left);}if (root.right != null) {rdeep = minDepth(root.right);}return Math.min(ldeep, rdeep) + 1;}

题目5 : 二叉树先序序列化和反序列化

注意：中序遍历无法完成二叉树的序列化和反序列化，代码中给出了说明。后序遍历可以但不再详述。

测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

思路

序列化
- 使用按照先序遍历的路线, 有值用StringBuilder追加 " 值 + ‘,’ “, 为空则追加”#,", 递归操作
反序列化
- 将拼接后的字符串用’,'分割为字符串数组, 使用全局变量 cnt来指示要处理的数组下标, 使用变量cur来读取当前正在处理的字符串
- 若cur为#, 返回null
- 若cur不为#, 则建立新的头结点, 赋值为cur的int值, 递归赋值左右节点, 返回头节点

代码O(n)

    // 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化// 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化// 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。// 比如如下两棵树//         __2//        ///       1//       和//       1__//          \//           2// 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}// 提交这个类public class Codec {public String serialize(TreeNode root) {StringBuilder builder = new StringBuilder();// 使用StringBuilderf(root, builder);// 递归调用序列化return builder.toString();}void f(TreeNode root, StringBuilder builder) {// 使用的是原来的builder, 返回void即可// 类似于二叉树的先序遍历if (root == null) {// 为null, 直接停builder.append("#,");// 占位} else {builder.append(root.val + ",");// 加值f(root.left, builder);// 左树序列化f(root.right, builder);// 右树序列化}}// 当前数组消费到哪了public static int cnt;// (全局变量方便)public TreeNode deserialize(String data) {String[] vals = data.split(",");// 用,分割出每一个值cnt = 0;// 要处理的字符下标return g(vals);// 递归消费}TreeNode g(String[] vals) {// !!!每个条件判断下都有一个出口String cur = vals[cnt++];// 用1个变量保存, 否则容易多++if (cur.equals("#")) {return null;// 空结点} else {TreeNode head = new TreeNode(Integer.valueOf(cur));// 建立有效结点head.left = g(vals);// 左树消费head.right = g(vals);// 右树消费return head;}}}

题目6 : 二叉树按层序列化和反序列化

测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

思路

序列化
- 先判空
- 层次遍历中, 每次进队列之前进行序列化
反序列化
- 先判空
- 将字符串分割, 依次消耗数组中的值
  - 先建立根结点, 根结点入队
  - 当队列中还有结点
    - 取出当前结点, 消耗当前后两位的值, 生成结点的左右孩子, 左右孩子中谁不为空,谁进队列,先加左,再加右
- 返回根结点

代码O(n)

	public class Codec {// 用于按层遍历public static int MAXN = 10001;public static TreeNode[] queue = new TreeNode[MAXN];public static int l, r;public String serialize(TreeNode root) {StringBuilder builder = new StringBuilder();if (root != null) {// 树不为空,追加字符串// 进队列之前,序列化builder.append(root.val + ",");// 初始化队列l = 0;r = 0;queue[r++] = root;while (l < r) {root = queue[l++];// 弹出当前结点if (root.left != null) {// 左孩子不为空// 进队列之前,序列化builder.append(root.left.val + ",");// 左孩子的值,不要写错!!!queue[r++] = root.left;} else {// 没有左: 序列化 但 不加到队列builder.append("#,");}if (root.right != null) {// 进队列之前,序列化builder.append(root.right.val + ",");// 右孩子的值,不要写错!!!queue[r++] = root.right;} else {// 没有右: 序列化 但 不加到队列builder.append("#,");}}// while}// endIf: 如果root==null,返回""(空串)return builder.toString();// 返回序列化后的字符串}public TreeNode deserialize(String data) {if (data.equals("")) {// root == nullreturn null;}String[] nodes = data.split(",");// 分割字符串int index = 0;// 当前消耗的下标TreeNode root = generate(nodes[index++]);// 建立根结点// 初始化队列l = 0;r = 0;queue[r++] = root;// 分割出的根结点 加入 队列while (l < r) {// 队列不为空TreeNode cur = queue[l++];// 弹出一个结点// 直接把根结点的左右孩子消费,建立出来cur.left = generate(nodes[index++]);cur.right = generate(nodes[index++]);// 左右孩子中谁不为空,谁进队列,先加左,再加右if (cur.left != null) {queue[r++] = cur.left;}if (cur.right != null) {queue[r++] = cur.right;}}// end whilereturn root;// 返回根结点}private TreeNode generate(String val) {return val.equals("#") ? null : new TreeNode(Integer.valueOf(val));}}

题目7 : 利用先序与中序遍历序列构造二叉树

测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
思路
- 特殊判断, 输入不合法的情况
- 根据先序遍历找出每一次递归的根结点, 使用根节点将中序遍历分为两半, 左半边为对应的左子树, 先序遍历中根节点以后数对应数目的结点也为左子树的节点; 右半边为对应的右子树, 先序遍历中根结点以后数对应数目的结点也为右子树的节点.
- 递归, 分别用以下方式递归构造左右子树: 给出先序遍历及处理子树下标范围, 给出中序遍历及处理子树下标范围, 根据第二点建立

代码O(n)

	public static TreeNode buildTree(int[] pre, int[] in) {// 特殊判断, 不合法情况if (pre == null || in == null || pre.length != in.length) {return null;}// 设置一张表, 用于加速查找对应节点在中序遍历的位置HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < in.length; i++) {map.put(in[i], i);}// 开始建树return f(pre, 0, pre.length - 1, in, 0, in.length - 1, map);// 输入的下标, 看好, 不要越界}public static TreeNode f(int[] pre, int l1, int r1, int[] in, int l2, int r2, HashMap<Integer, Integer> map) {// 特殊判断, 不合法情况if (l1 > r1) {return null;}// 建头结点TreeNode head = new TreeNode(pre[l1]);// 只有一个数, 直接返回头结点即可if (l1 == r1) {return head;}// 查出中序遍历的位置int k = map.get(pre[l1]);// pre : l1(........)[.......r1]// in  : (l2......)k[........r2]// (...)是左树对应，[...]是右树的对应head.left = f(pre, l1 + 1, l1 + k - l2, in, l2, k - 1, map);head.right = f(pre, l1 + k - l2 + 1, r1, in, k + 1, r2, map);return head;}

题目8 : 验证完全二叉树

测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
思路
- 使用BFS, 挨个遍历, 判断每一个节点是否违规
  - 第一个违规条件: 当前节点有右子树无左子树
  - 第二个违规条件: 遇到过孩子不双全的节点 且 当前结点不是叶节点
- 若出现违规节点, 则该二叉树不是完全二叉树
- 若所有节点都符合要求, 则该二叉树是完全二叉树 (空树是完全二叉树)

代码O(n)

	// 如果测试数据量变大了就修改这个值// 用于BFSpublic static int MAXN = 101;public static TreeNode[] queue = new TreeNode[MAXN];public static int l, r;public static boolean isCompleteTree(TreeNode h) {if (h == null) {// 判空return true;}// BFSl = r = 0;queue[r++] = h;// 是否遇到过左右两个孩子不双全的节点boolean leaf = false;// 开始遍历while (l < r) {// 1.弹出一个结点h = queue[l++];// 2.判断是不是违规// 第一个违规条件: 有右无左			第二个违规条件: 遇到过孩子不双全的节点 且 该结点不是叶节点if ((h.left == null && h.right != null) || (leaf && (h.left != null || h.right != null))) {return false;}// 3.BFSif (h.left != null) {queue[r++] = h.left;}if (h.right != null) {queue[r++] = h.right;}// 4.判断该节点是不是孩子不双全节点if (h.left == null || h.right == null) {// h.left == null: 左右孩子都没有; h.right == null: 没有右孩子leaf = true;}}// end whilereturn true;// 没有违规, 返回true}

题目9 : 求完全二叉树的节点个数，要求时间复杂度低于O(n)

测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/
思路
- 递归
- 根据根节点右子树的最左节点 能否到达最深层, 从而判断出为满二叉树的一侧和需要进行递归计算的一侧
  - 若能到达最深层, 说明根节点的左子树为满二叉树, 节点个数为 2^(子树深度) - 1, 左子树节点个数加上根节点个数后的总节点个数为2^(子树深度); 右子树一定为完全二叉树, 递归调用即可
  - 若不能到达最深层, 说明根节点的右子树为满二叉树, 且右子树的深度比根结点所在树的深度少1, 节点个数为2^(子树深度) - 1, 右子树节点个数加上根节点个数后的总节点个数为2^(子树深度); 左子树一定为完全二叉树, 递归调用即可

代码O(h^2) h == log2(n)

	public static int countNodes(TreeNode head) {// 判空if (head == null) {return 0;}return f(head, 1, mostLeft(head, 1));}// cur : 当前来到的节点// level :  当前来到的节点在第几层// h : 整棵树的高度，不是cur这棵子树的高度// 求 : cur这棵子树上有多少节点public static int f(TreeNode cur, int level, int h) {// BaseCase: 当前结点就是最深层的结点 即 叶子结点if (level == h) {return 1;// 只有这一个结点}// 判断cur右树上的最左节点 是否 到达最深层, 从而判断出为 满二叉树的一侧 和 需要递归调用的一侧if (mostLeft(cur.right, level + 1) == h) {// cur右树上的最左节点，扎到了最深层return (1 << (h - level)) + f(cur.right, level + 1, h);// 	cur左树 + 我自己 的深度  cur右树递归计算} else {// cur右树上的最左节点，没扎到最深层return (1 << (h - level - 1)) + f(cur.left, level + 1, h);// cur右树 + 我自己 的深度      cur左树递归计算}}// 当前节点是cur，并且它在level层// 返回从cur开始不停往左，能扎到几层public static int mostLeft(TreeNode cur, int level) {while (cur != null) {// 不能用cur.left判断, 因为cur可能为空level++;cur = cur.left;}return level - 1;}