二叉树
- 二叉树
- 构造二叉树
- 寻找重复子树
图片来源于网络
1. 二叉树
基本二叉树节点如下：
/**
* 基本二叉树节点
*/
class TreeNode {
int val;
TreeNode left, right;
public TreeNode(int val) {
this.val = val;
}
}
很多经典算法，比如回溯、动态规划、分治算法等都是树的问题，而树的问题就离不开树的递归遍历框架：
/**
* 二叉树遍历框架
*/
void traverse(TreeNode root) {
// 前序遍历：根左右
traverse(root.left)
// 中序遍历：左根右
traverse(root.right)
// 后序遍历：左右根
}
举个例子，经典算法「快速排序」就是个二叉树的前序遍历，「归并排序」就是个二叉树的后续遍历。
快速排序的代码框架如下：
/**
* 快速排序框架
* <p>
* 对 nums[low..high] 进行排序，先找一个分界点p，
* 通过交换元素使得 nums[low..p-1] 都小于等于 nums[p]，且 nums[p+1..high] 都大于 nums[p]，
* 然后递归地去 nums[low..p-1] 和 nums[p+1..high] 中寻找新的分界点，最后整个数组就被排序了
*/
void quickSort(int[] nums, int low, int high) {
/* **** 前序遍历位置 ******/
// 通过交换元素构建分界点 p
int p = partition(nums, low, high);
/* ************************/
quickSort(nums, low, p - 1);
quickSort(nums, p + 1, high);
}
归并排序的代码框架如下：
/**
* 归并排序的框架
* <p>
* 对 nums[low..high] 进行排序，先对 nums[low..mid] 排序，再对 nums[mid+1..high] 排序，
* 最后把这两个有序的子数组合并，整个数组就排好序了。
*/
void mergeSort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
mergeSort(nums, low, mid);
mergeSort(nums, mid + 1, high);
/* ***** 后序遍历位置 ******/
// 合并两个排好序的子数组
merge(nums, low, mid, high);
/* ************************/
}
如何写递归算法？
写递归算法的关键是要明确函数的「定义」是什么，然后相信这个定义，利用这个定义推导最终结果，绝不要试图跳入递归。
如计算一棵二叉树共有几个节点：
/**
* 计算一棵二叉树共有几个节点
* <p>
* 定义：count(root) 返回以 root 为根的树有多少节点
*/
private int count(TreeNode root) {
// base case
if (root == null) return 0;
// 自己加上子树的节点数就是整棵树的节点数
return 1 + count(root.left) + count(root.right);
}
写树相关的算法，先搞清楚当前 root 节点该做什么，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。
1.1 翻转二叉树
力扣第 226 题「翻转二叉树」：
翻转二叉树
上述题目只要把二叉树上的每一个节点的左右子节点进行交换，最后的结果就是完全翻转之后的二叉树，代码如下：
/**
* 翻转二叉树：将整棵树的节点翻转
*/
private TreeNode invertTree(TreeNode root) {
// base case
if (root == null) return null;
/* *** 前序遍历位置 ****/
// root 节点需要交换它的左右子节点
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 让左右子节点继续翻转它们的子节点
invertTree(root.left);
invertTree(root.right);
return root;
}
值得注意的是：二叉树题目的一个难点就是，如何把题目的要求细化成每个节点需要做的事情。
1.2 填充二叉树节点的右侧指针
力扣第 116 题「填充每个节点的下一个右侧节点指针」：
填充二叉树节点的右侧指针
输入是一棵「完美二叉树」，即除了最右侧的节点 next 指针会指向 null，其他节点的右侧一定有相邻的节点，容易写下如下代码：
TreeNode connect(TreeNode root) {
if(root == null || root.left == null) return root;
root.left.next = root.right;
connect(root.left);
connect(root.right);
return root;
}
上述代码存在一个问题，当两个子节点不属于同一个父节点时，就没法连接起来，即只依赖一个节点的话，是没办法连接「跨父节点」的两个相邻节点的。
因此需要增加函数参数，给他安排两个节点，「将每一层二叉树节点连接起来」可以细化成「将每两个相邻节点都连接起来」：
/**
* 填充二叉树节点的右侧指针
* <p>
* 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。
* 填充它的每个 next 指针，让这个指针指向其下一个右侧节点，若无右侧节点将 next 指针设为 null
* 初始状态下，所有 next 指针都被设置为 null
*/
private TreeNode connect(TreeNode root) {
if (root == null) return null;
connectTwoNode(root.left, root.right);
return root;
}
/**
* 定义：输入两个节点，将它俩连接起来
* <p>
* connectTwoNode 函数不断递归，可以无死角覆盖整棵二叉树，将所有相邻节点都连接起来
*/
private void connectTwoNode(TreeNode node1, TreeNode node2) {
if (node1 == null || node2 == null) return;
/* *** 前序遍历位置 ****/
// 将传入的两个节点连接
node1.next = node2;
// 连接相同父节点的两个子节点
connectTwoNode(node1.left, node1.right);
connectTwoNode(node2.left, node2.right);
// 连接跨越父节点的两个子节点
connectTwoNode(node1.right, node2.left);
}
1.3 将二叉树展开为链表
力扣第 114 题「二叉树展开为链表」：
二叉树展开为链表
函数签名如下：
void flatten(TreeNode root);
尝试给出这个函数的定义，给 flatten 函数输入一个节点 root，那么以 root 为根的二叉树就会被拉平为一条链表：
/**
* 将二叉树展开为链表
* <p>
* 定义：将以 root 为根的树拉平为链表
*/
private void flatten(TreeNode root) {
// base case
if (root == null) return;
flatten(root.left);
flatten(root.right);
/* *** 后序遍历位置 ****/
// 1、左右子树已经被拉平成一条链表
TreeNode left = root.left;
TreeNode right = root.right;
// 2、将左子树作为右子树
root.left = null;
root.right = left;
// 3、将原先的右子树接到当前右子树的末端
TreeNode p = root;
while (p.right != null) {
// 遍历 root 直到 root.right == null
p = p.right;
}
p.right = right; // 接上原先的右子树
}
还是那句话：只要知道 flatten 的定义如此，相信这个定义，让 root 做它该做的事情，然后 flatten 函数就会按照定义工作。
2. 构造二叉树
树的算法，关键思路如下：
把题目的要求细化，搞清楚根节点应该做什么，然后剩下的事情抛给前/中/后序的遍历框架就行了，而不要试图跳进递归的细节里。
2.1 构造最大二叉树
对于构造二叉树的问题，根节点要做的就是把想办法把自己构造出来。
/**
* 最大二叉树
* <p>
* 给定一个不含重复元素的整数数组。最大二叉树定义如下：
* 1. 二叉树的根是数组中的最大元素
* 2. 左子树是通过数组中最大值左边部分构造出的最大二叉树
* 3. 右子树是通过数组中最大值右边部分构造出的最大二叉树
* <p>
* 通过给定的数组构建最大二叉树，并输出这个树的根节点
* 如 输入 [3, 2, 1, 6, 0, 5]，输出如下：
* // 6
* // / \
* // 3 5
* // \ /
* // 2 0
* // \
* // 1
*/
private TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, 0, nums.length - 1);
}
/**
* 将 nums[low..high] 构造成符合条件的树，返回根节点
*/
private TreeNode build(int[] nums, int low, int high) {
// base case
if (low > high) return null;
// 找到数组中的最大值和对应的索引
int index = -1, maxVal = Integer.MIN_VALUE;
for (int i = low; i <= high; i++) {
if (maxVal < nums[i]) {
index = i;
maxVal = nums[i];
}
}
TreeNode root = new TreeNode(maxVal);
// 递归调用构造左右子树
root.left = build(nums, low, index - 1);
root.right = build(nums, index + 1, high);
return root;
}
上述代码，遍历数组把找到最大值 maxVal，把根节点 root 做出来，然后对 maxVal 左边的数组和右边的数组进行递归调用，作为 root 的左右子树。
对于每个根节点，只需要找到当前 nums 中的最大值和对应的索引，然后递归调用左右数组构造左右子树即可。
2.2 通过前序和中序遍历结果构造二叉树
类似上一题，想办法确定根节点的值，把根节点做出来，然后递归构造左右子树即可。
/**
* 通过前序和中序遍历结果构造二叉树
* <p>
* 根据一棵树的前序遍历与中序遍历构造二叉树
* 假设树中没有重复的元素，例如给出：
* 前序遍历 preorder = [3, 9, 20, 15, 7]
* 中序遍历 inorder = [9, 3, 15, 20, 7]
* 返回如下的二叉树：
* // 3
* // / \
* // 9 20
* // / \
* // 15 7
* <p>
* tip: 想办法确定根节点的值，把根节点做出来，然后递归构造左右子树即可
*/
private TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
/**
* 前序遍历数组为 preorder[preStart..preEnd]，
* 中序遍历数组为 inorder[inStart..inEnd]，
* 构造二叉树，返回该二叉树的根节点
*/
private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
// base case
if (preStart > preEnd) return null;
// root 节点对应的值就是前序遍历数组的第一个元素
int rootVal = preorder[preStart];
// rootVal 在中序遍历数组中的索引
int index = 0;
for (int i = inStart; i < inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
TreeNode root = new TreeNode(rootVal);
// 递归构造左右子树
int leftSize = index - inStart; // 左子树的节点数
root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);
root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);
return root;
}
根据前序遍历和中序遍历结果的特点，确定根节点、左右数组对应的起始索引和终止索引。
2.3 通过后序和中序遍历结果构造二叉树
和上面的区别是，后序遍历和前序遍历相反，根节点对应的值为后序遍历的最后一个元素：
/**
* 通过后序和中序遍历结果构造二叉树
* <p>
* 根据一棵树的前序遍历与中序遍历构造二叉树
* 假设树中没有重复的元素，例如给出：
* 中序遍历 inorder = [9, 3, 15, 20, 7]
* 后序遍历 postorder = [9, 15, 7, 20, 3]
* 返回如下的二叉树：
* // 3
* // / \
* // 9 20
* // / \
* // 15 7
* <p>
* tip: 想办法确定根节点的值，把根节点做出来，然后递归构造左右子树即可
*/
private TreeNode buildTree2(int[] inorder, int[] postorder) {
return build2(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
private TreeNode build2(int[] inorder, int inStart, int inEnd, int[] postOrder, int postStart, int postEnd) {
if (inStart > inEnd) return null;
// root 节点对应的值就是后序遍历数组的最后一个元素
int rootVal = postOrder[postEnd];
// rootVal 在中序遍历数组中的索引
int index = 0;
for (int i = 0; i < inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
TreeNode root = new TreeNode(rootVal);
// 递归构造左右子树
int leftSize = index - inStart; // 左子树的节点数
root.left = build2(inorder, inStart, index - 1, postOrder, postStart, postStart + leftSize - 1);
root.right = build2(inorder, index + 1, inEnd, postOrder, postStart + leftSize, postEnd - 1);
return root;
}
3. 寻找重复子树
/**
* 652 题「寻找重复子树」
* <p>
* 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，只需要返回其中任意一棵的根节点即可。
* <p>
* 两棵树重复是指它们具有相同的结构以及相同的节点值
* <p>
* 如： 其中： 和 是重复的子树
* // 1 2 4
* // / \ /
* // 2 3 4
* // / / \
* // 4 2 4
* // /
* // 4
*/
private List<TreeNode> findDuplicateSubtrees(TreeNode root) {
traverseTree(root);
return res;
}
// 记录所有子树以及出现的次数
private HashMap<String, Integer> memo = new HashMap<>();
// 记录重复的子树根节点
private LinkedList<TreeNode> res = new LinkedList<>();
// 辅助函数
private String traverseTree(TreeNode root) {
if (root == null) return "#";// 对于空节点，可以用一个特殊字符表示
// 将左右子树序列化成字符串
String left = traverseTree(root.left);
String right = traverseTree(root.right);
// 左右子树加上自己，就是以自己为根的二叉树序列化结果
String subTree = left + "," + right + "," + root.val;
// if (memo.containsKey(subTree)){
// // 有人和我重复，把自己加入结果列表
// res.add(root);
// } else {
// // 暂时没人跟我重复，把自己加入集合
// memo.put(subTree)
// }
// 获取 subTree 在 memo 中的次数，默认是 0
int freq = memo.getOrDefault(subTree, 0);
if (freq == 1) {
// 多次重复也只会被加入结果集一次
res.add(root);
}
// 给子树对应的出现次数加一
memo.put(subTree, freq + 1);
return subTree;
}
总结：做二叉树的问题，关键是把题目的要求细化，搞清楚根节点应该做什么，然后剩下的事情抛给前/中/后序的遍历框架就行了。
参考链接：
网友评论