构造二叉树
思路：
- 根据中序遍历找到根节点，在前序遍历或者后序遍历中计算左右子树的范围；
- 之后递归实现。
例题：
- 105. 从前序与中序遍历序列构造二叉树
- 106. 从中序与后序遍历序列构造二叉树
- 889. 根据前序和后序遍历构造二叉树（根据前序遍历找到左子树的根节点，在后序遍历中找到对应下标并计算左子树的范围）
完全二叉树
958. 二叉树的完全性检验
两个条件:
- 左孩子为空，右孩子不为空不是完全二叉树；
- 遇到左孩子或者右孩子为空的节点，下一次遍历的时候以后的所有节点都应该没有左孩子和右孩子。
核心代码：
左孩子为空、右孩子不为空一定不是完全二叉树
if(node.left == null && node.right != null){
return false;
}
如果叶子节点左孩子、右孩子不为空一定不是完全二叉树
if(flag && (node.left != null || node.right != null)){
return false;
}
临界点、从该节点之后的所有节点都是叶子节点
if(node.left == null || node.right == null){
flag = true;
}
剑指 Offer II 043. 往完全二叉树添加节点 / 919. 完全二叉树插入器
分解为：
- 层序遍历二叉树，用list存储；
- 根据二叉树的性质寻找当前节点的父节点的下标（i - 1）/ 2。
根据二叉树的性质寻找父节点的下标（i - 1）/ 2
TreeNode parent = list.get((list.size() - 2) / 2);
if(parent.left == null){
parent.left = node;
}else if(parent.right == null){
parent.right = node;
}
满二叉树
分解为：
- 求二叉树的深度 h + 求节点的个数 n；
- 满足 n == 1 << h - 1;
二叉树的深度
public int height(TreeNode root){
if(root == null){
return 0;
}
int left = height(root.left);
int right = height(root.right);
return Math.max(left, right) + 1;
}
平衡二叉树
面试题 04.04. 检查平衡性 / 110. 平衡二叉树 / 剑指 Offer 55 - II. 平衡二叉树
分解为：
- 求二叉树的左右子树的深度；
- 递归到二叉树的左右子树。
求二叉树的深度同上；
二叉搜索树
701. 二叉搜索树中的插入操作
思路：根据二叉搜索树的性质找到对应的叶子节点，比较此叶子节点与val进行左、右插入
核心代码：
class Solution {
// 思路：根据二叉树的性质找到对应的叶子节点进行插入
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null){
return new TreeNode(val);
}
TreeNode cur = root, parent = null;
while(cur != null){
parent = cur;
if(cur.val < val){
cur = cur.right;
}else{
cur = cur.left;
}
}
TreeNode node = new TreeNode(val);
if(parent.val < val){
parent.right = node;
}else{
parent.left = node;
}
return root;
}
}
450. 删除二叉搜索树中的节点
思路：
- 如果当前节点有右子树，找到右子树的最小值赋值给根节点，之后删除右子树的最小值；
- 如果当前节点有左子树，找到左子树的最大值赋值给根节点，之后删除左子树的最大值。
核心代码：
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null){
return root;
}else if(root.val < key){
root.right = deleteNode(root.right, key);
}else if(root.val > key){
root.left = deleteNode(root.left, key);
}else{
if(root.left == null && root.right == null){
return null;
}else if(root.left != null){
root.val = leftMax(root);
root.left = deleteNode(root.left, root.val);
}else{
root.val = rightMin(root);
root.right = deleteNode(root.right, root.val);
}
}
return root;
}
public int leftMax(TreeNode root){
root = root.left;
while(root.right != null){
root = root.right;
}
return root.val;
}
public int rightMin(TreeNode root){
root = root.right;
while(root.left != null){
root = root.left;
}
return root.val;
}
}
510. 二叉搜索树中的中序后继 II
思路：
- 如果当前节点有右子树，则寻找右子树中最左的节点；
- 如果没有，说明当前节点为最右侧节点，则一直寻找祖先节点。
class Solution {
public Node inorderSuccessor(Node node) {
// 如果有右子树，但是是最左边的节点
// 如果没有，需要一直向上找祖先节点
if(node.right != null){
node = node.right;
while(node.left != null){
node = node.left;
}
return node;
}else{
while(node.parent != null && node.parent.right == node){
node = node.parent;
}
return node.parent;
}
}
}
预存上一个节点与当前节点比较
分解为：
- 中序遍历；
- 预存储前一个节点与当前节点比较，比较之后节点再次更新为当前节点。
98. 验证二叉搜索树的核心代码：
if(pre != null && pre.val >= root.val){
flag = false;
}
pre = root;
99. 恢复二叉搜索树的核心代码：
inorder(root.left);
if(pre != null && pre.val > root.val){
// 定位两个错误的节点
if(a == null){
a = pre;
}
b = root;
}
pre = root;
inorder(root.right);
- 剑指 Offer II 053. 二叉搜索树中的中序后继
- 285. 二叉搜索树中的中序后继
- 面试题 04.06. 后继者
核心代码：
public void dfs(TreeNode root, TreeNode p) {
if(root == null){
return;
}
dfs(root.left, p);
if(pre != null && pre.val == p.val){
cur = root;
}
pre = root;
dfs(root.right, p);
}
剑指 Offer II 052. 展平二叉搜索树
思路：在中序遍历的时候构造一直向右的二叉树
核心代码：
public void dfs(TreeNode root){
if(root == null){
return;
}
dfs(root.left);
// 添加节点
node.right = new TreeNode(root.val);
// 继续向右节点添加
node = node.right;
dfs(root.right);
}
剑指 Offer II 055. 二叉搜索树迭代器 / 173. 二叉搜索树迭代器
中序遍历：
public void serialize(List<Integer> deque, TreeNode root){
if(root == null){
return;
}
serialize(deque, root.left);
deque.add(root.val);
serialize(deque, root.right);
}
剑指 Offer 36. 二叉搜索树与双向链表
中序遍历的时候构造前驱和后继
核心代码：if(pre == null){
当前cur没有左节点，也就是cur为头节点
cur = root;
}else{
正常情况
pre.right = root;
}
root.left = pre;
pre = root;
构造搜索二叉树
数组篇：
- 面试题 04.02. 最小高度树（转义为：构造二叉搜索树）
- 108. 将有序数组转换为二叉搜索树
-
1382. 将二叉搜索树变平衡（转义为：中序遍历 + 构造二叉搜索树）
核心代码：
private TreeNode buildTree(int[] nums, int left, int right) {
if (left <= right) {
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = buildTree(nums, left, mid - 1);
root.right = buildTree(nums, mid + 1, right);
return root;
}
return null;
}
链表篇：
- 109. 有序链表转换二叉搜索树
核心代码：快慢指针找到中间位置，之后再进行构造二叉树
public TreeNode sortedListToBST(ListNode left, ListNode right) {
if(left == right){
return null;
}
// 快慢指针
ListNode fast = left, slow = left;
while(fast.next != right && fast.next.next != right){
fast = fast.next.next;
slow = slow.next;
}
//构造二叉树
TreeNode root = new TreeNode(slow.val);
root.left = sortedListToBST(left, slow);
root.right = sortedListToBST(slow.next, right);
return root;
}
二叉树的序列化与反序列化
分解为：二叉树的序列化 + 构造二叉树
题目：
（通解：前序遍历）
- 剑指 Offer 37. 序列化二叉树
- 剑指 Offer II 048. 序列化与反序列化二叉树
- 297. 二叉树的序列化与反序列化
- 449. 序列化和反序列化二叉搜索树
核心代码：
public void serialize(TreeNode root, StringBuffer buffer) {
if(root == null){
buffer.append("null").append(",");
}else{
buffer.append(root.val).append(",");
serialize(root.left, buffer);
serialize(root.right, buffer);
}
}
public TreeNode deserialize(Deque<String> deque) {
String temp = deque.poll();
if(temp.equals("null")){
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(temp));
root.left = deserialize(deque);
root.right = deserialize(deque);
return root;
}
（层序遍历）在for循环里面递归
- 428. 序列化和反序列化 N 叉树
核心代码：
public void serialize(StringBuffer buffer, Node root) {
if(root == null){
buffer.append("null").append(",");
}else{
// 层序遍历
buffer.append(root.val).append(":").append(root.children.size()).append(",");
for(Node node : root.children){
serialize(buffer, node);
}
}
}
public Node deserialize(Deque<String> deque) {
if(deque.peek().equals("null")){
return null;
}
String[] temp = deque.poll().split(":");
int val = Integer.valueOf(temp[0]);
int nums = Integer.valueOf(temp[1]);
Node root = new Node(val);
root.children = new ArrayList<>();
for(int i = 0; i < nums; i++){
root.children.add(deserialize(deque));
}
return root;
}
最近公共祖先节点
二叉搜索树的最近公共祖先节点
- 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
- 235. 二叉搜索树的最近公共祖先
核心代码：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || p == root || q == root){
return root;
}
if(p.val > root.val && q.val > root.val){
return lowestCommonAncestor(root.right, p, q);
}
if(p.val < root.val && q.val < root.val){
return lowestCommonAncestor(root.left, p, q);
}
return root;
}
}
二叉树的最近公共祖先节点
- 236. 二叉树的最近公共祖先
- 剑指 Offer 68 - II. 二叉树的最近公共祖先
核心代码：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || p == root || q == root){
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null){
return root;
}else if(left != null){
return left;
}else if(right != null){
return right;
}
return null;
}
}
改进求最近公共祖先
- 1644. 二叉树的最近公共祖先 II
区别：增加判断节点是否在二叉树中
public boolean isExits(TreeNode root, TreeNode temp) {
if(root == null){
return false;
}
return root.val == temp.val || isExits(root.left, temp) || isExits(root.right, temp);
}
- 1650. 二叉树的最近公共祖先 III
class Solution {
public Node lowestCommonAncestor(Node p, Node q) {
// 有parent节点也就相当于链表
Node a = p, b = q;
while(a != b){
a = a.parent == null ? q : a.parent;
b = b.parent == null ? p : b.parent;
}
return a;
}
}
- 1676. 二叉树的最近公共祖先 IV
区别：多个节点的公共祖先，判断条件更改为是否包含
public TreeNode lowestCommonAncestor(TreeNode root, Set<Integer> set) {
if(root == null){
return root;
}
if(set.contains(root.val)){
return root;
}
TreeNode left = lowestCommonAncestor(root.left, set);
TreeNode right = lowestCommonAncestor(root.right, set);
if(left != null && right != null){
return root;
}else if(left != null){
return left;
}else if(right != null){
return right;
}
return null;
}
根据深度进行判断返回节点，感觉有些类似于搜索二叉树寻找最近公共祖先了
- 865. 具有所有最深节点的最小子树
- 1123. 最深叶节点的最近公共祖先
核心代码：
class Solution {
public TreeNode subtreeWithAllDeepest(TreeNode root) {
if(root == null){
return root;
}
int left = deepth(root.left);
int right = deepth(root.right);
if(left == right){
return root;
}else if(left > right){
return subtreeWithAllDeepest(root.left);
}else{
return subtreeWithAllDeepest(root.right);
}
}
public int deepth(TreeNode root) {
if(root == null){
return 0;
}
int left = deepth(root.left);
int right = deepth(root.right);
return Math.max(left, right) + 1;
}
}
折纸问题
分解为：
- 中序遍历；
- 左孩子：down，右孩子：up。
核心代码：
public void dfs(List<String> list, int i, int n, boolean flag) {
// write code here
if(i > n){
return;
}
dfs(list, i + 1, n, true);
list.add(flag ? "down" : "up");
dfs(list, i + 1, n, false);
}
层序遍历（广度优先遍历）
- 515. 在每个树行中找最大值
- 429. N 叉树的层序遍历
- 637. 二叉树的层平均值
- 199. 二叉树的右视图
- 102. 二叉树的层序遍历
- 107. 二叉树的层序遍历 II
核心代码：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> list = new ArrayList<>();
if(root == null){
return list;
}
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> temp = new ArrayList<>();
for(int i = queue.size(); i > 0; i--){
TreeNode node = queue.poll();
temp.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
list.add(temp);
}
return list;
}
}
- 117. 填充每个节点的下一个右侧节点指针 II
- 116. 填充每个节点的下一个右侧节点指针
Node node = deque.poll();
if(i > 0){
node.next = deque.peek();
}
深度优先遍历
- 104. 二叉树的最大深度
- 111. 二叉树的最小深度（多加了左、右子树是否为空的判断条件）
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
if(root.left == null && root.right != null){
return minDepth(root.right) + 1;
}
if(root.left != null && root.right == null){
return minDepth(root.left) + 1;
}
int left = minDepth(root.left);
int right = minDepth(root.right);
return Math.min(left, right) + 1;
}
京公网安备 11010502036488号