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

class036 二叉树高频题目-上-不含树型dp【算法】

article 2024/11/14 23:07:05

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

在这里插入图片描述
在这里插入图片描述

code1 102. 二叉树的层序遍历

// 二叉树的层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/

code1 普通bfs
code2 一次操作一层

package class036;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 二叉树的层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/
public class Code01_LevelOrderTraversal {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;
	}

	// 提交时把方法名改为levelOrder，此方法为普通bfs，此题不推荐
	public static List<List<Integer>> levelOrder1(TreeNode root) {
		List<List<Integer>> ans = new ArrayList<>();
		if (root != null) {
			Queue<TreeNode> queue = new LinkedList<>();
			HashMap<TreeNode, Integer> levels = new HashMap<>();
			queue.add(root);
			levels.put(root, 0);
			while (!queue.isEmpty()) {
				TreeNode cur = queue.poll();
				int level = levels.get(cur);
				if (ans.size() == level) {
					ans.add(new ArrayList<>());
				}
				ans.get(level).add(cur.val);
				if (cur.left != null) {
					queue.add(cur.left);
					levels.put(cur.left, level + 1);
				}
				if (cur.right != null) {
					queue.add(cur.right);
					levels.put(cur.right, level + 1);
				}
			}
		}
		return ans;
	}

	// 如果测试数据量变大了就修改这个值
	public static int MAXN = 2001;

	public static TreeNode[] queue = new TreeNode[MAXN];

	public static int l, 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++) {
					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);
			}
		}
		return ans;
	}

}

code2 103. 二叉树的锯齿形层序遍历

// 二叉树的锯齿形层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

code 遍历

package class036;

import java.util.ArrayList;
import java.util.List;

// 二叉树的锯齿形层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
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>();
				// reverse == false, 左 -> 右， l....r-1, 收集size个
				// reverse == true,  右 -> 左， r-1....l, 收集size个
				// 左 -> 右, i = i + 1
				// 右 -> 左, i = i - 1
				for (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);
				}
				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;
	}

}

code3 662. 二叉树最大宽度

// 二叉树的最大特殊宽度
// 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/

package class036;

// 二叉树的最大特殊宽度
// 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/
public class Code03_WidthOfBinaryTree {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;
	}

	// 提交以下的方法
	// 用每次处理一层的优化bfs就非常容易实现
	// 如果测试数据量变大了就修改这个值
	public static int MAXN = 3001;

	public static TreeNode[] nq = new TreeNode[MAXN];

	public static int[] iq = new int[MAXN];

	public static int l, r;

	public static int widthOfBinaryTree(TreeNode root) {
		int ans = 1;
		l = r = 0;
		nq[r] = root;
		iq[r++] = 1;
		while (l < r) {
			int size = r - l;
			ans = Math.max(ans, iq[r - 1] - iq[l] + 1);
			for (int i = 0; i < size; i++) {
				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;
				}
			}
		}
		return ans;
	}

}

code4 104. 二叉树的最大深度 111. 二叉树的最小深度

// 求二叉树的最大、最小深度
// 测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/
// 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/

package class036;

// 求二叉树的最大、最小深度
public class Code04_DepthOfBinaryTree {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;
	}

	// 测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/
	public static int maxDepth(TreeNode root) {
		return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
	}

	// 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/
	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;
	}

}

code5 297. 二叉树的序列化与反序列化

// 二叉树先序序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

package class036;

// 二叉树先序序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Code05_PreorderSerializeAndDeserialize {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(int v) {
			val = v;
		}
	}

    // 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化
    // 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
    // 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
    // 比如如下两棵树
    //         __2
    //        /
    //       1
    //       和
    //       1__
    //          \
    //           2
    // 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
	// 提交这个类
	public class Codec {

		public String serialize(TreeNode root) {
			StringBuilder builder = new StringBuilder();
			f(root, builder);
			return builder.toString();
		}

		void f(TreeNode root, StringBuilder builder) {
			if (root == null) {
				builder.append("#,");
			} else {
				builder.append(root.val + ",");
				f(root.left, builder);
				f(root.right, builder);
			}
		}

		public TreeNode deserialize(String data) {
			String[] vals = data.split(",");
			cnt = 0;
			return g(vals);
		}

		// 当前数组消费到哪了
		public static int cnt;

		TreeNode g(String[] vals) {
			String cur = vals[cnt++];
			if (cur.equals("#")) {
				return null;
			} else {
				TreeNode head = new TreeNode(Integer.valueOf(cur));
				head.left = g(vals);
				head.right = g(vals);
				return head;
			}
		}

	}

}

code6 105. 从前序与中序遍历序列构造二叉树

// 利用先序与中序遍历序列构造二叉树
// 测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

package class036;

// 二叉树按层序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Code06_LevelorderSerializeAndDeserialize {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(int v) {
			val = v;
		}
	}

	// 提交这个类
	// 按层序列化
	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("#,");
					}
				}
			}
			return builder.toString();
		}

		public TreeNode deserialize(String data) {
			if (data.equals("")) {
				return 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;
				}
			}
			return root;
		}

		private TreeNode generate(String val) {
			return val.equals("#") ? null : new TreeNode(Integer.valueOf(val));
		}

	}

}

code7 958. 二叉树的完全性检验

// 验证完全二叉树
// 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/

1)无左有右 flase
2)孩子不全开始 必须都是叶子结点，否则false

package class036;

import java.util.HashMap;

// 利用先序与中序遍历序列构造二叉树
// 测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
public class Code07_PreorderInorderBuildBinaryTree {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(int v) {
			val = v;
		}
	}

	// 提交如下的方法
	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;
	}

}

code8 222. 完全二叉树的节点个数

// 求完全二叉树的节点个数
// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/

package class036;

// 验证完全二叉树
// 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
public class Code08_CompletenessOfBinaryTree {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;
	}

	// 提交以下的方法
	// 如果测试数据量变大了就修改这个值
	public 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;
		}
		l = r = 0;
		queue[r++] = h;
		// 是否遇到过左右两个孩子不双全的节点
		boolean leaf = false;
		while (l < r) {
			h = queue[l++];
			if ((h.left == null && h.right != null) || (leaf && (h.left != null || h.right != null))) {
				return false;
			}
			if (h.left != null) {
				queue[r++] = h.left;
			}
			if (h.right != null) {
				queue[r++] = h.right;
			}
			if (h.left == null || h.right == null) {
				leaf = true;
			}
		}
		return true;
	}

}

code9 222. 完全二叉树的节点个数

// 求完全二叉树的节点个数
// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/

package class036;

// 求完全二叉树的节点个数
// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/
public class Code09_CountCompleteTreeNodes {

	// 不提交这个类
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;
	}

	// 提交如下的方法
	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) {
		if (level == h) {
			return 1;
		}
		if (mostLeft(cur.right, level + 1) == h) {
			// cur右树上的最左节点，扎到了最深层
			return (1 << (h - level)) + f(cur.right, level + 1, h);
		} else {
			// cur右树上的最左节点，没扎到最深层
			return (1 << (h - level - 1)) + f(cur.left, level + 1, h);
		}
	}

	// 当前节点是cur，并且它在level层
	// 返回从cur开始不停往左，能扎到几层
	public static int mostLeft(TreeNode cur, int level) {
		while (cur != null) {
			level++;
			cur = cur.left;
		}
		return level - 1;
	}

}

http://www.kler.cn/a/161475.html

相关文章：

  • MyBatis CRUD快速入门
  • 阿里巴巴通义灵码推出Lingma SWE-GPT：开源模型的性能新标杆
  • YUM 的使用
  • Autosar CP DDS规范导读
  • 安全生产管理的重要性：现状、痛点与改进之路
  • 3.5【数据库系统】ER图
  • java设计模式学习之【组合模式】
  • hql面试题之字符串使用split分割，并选择其中的一部分字段的问题
  • /usr/bin/ld: cannot find -ltinfo 的解决方法
  • 第二十一章——网络通信
  • 使用Jython将Python代码转换为Java可执行文件
  • 手把手将Visual Studio Code变成Python开发神器
  • RabbitMQ 的七种消息传递形式
  • 结构体对齐和补齐
  • HarmonyOS开发(十)：通知和提醒
  • 洛谷P1044 [NOIP2003 普及组] 栈 递归方法
  • JVM中 Minor GC 和 Full GC 的区别
  • React中的空标签与Fragment标签的区别
  • 【数据库设计和SQL基础语法】--表的创建与操作--插入、更新和删除数据
  • Nginx（配置SLL证书）
  • 重生奇迹mu武器镶嵌顺序
  • MySQL学习day05
  • C++ STL容器与常用库函数
  • 一则广告，一个故事，这就我选择学习计算机专业的两个原因
  • 中国证券交易所有哪些
  • vs2022 winform 使用LiveCharts.Wpf控件出现黑框 去除方法