Java教程
算法—二叉树
写树相关的算法，先搞清楚当前root节点该做什么，以及什么时候做，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。
二叉树遍历框架
/* 二叉树遍历框架 */
void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}
快速排序和归并排序
快速排序的逻辑：若要对 nums[lo..hi] 进行排序，先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组被排序。
代码：
void sort(int[] nums, int lo, int hi) {
/****** 前序遍历位置 ******/
// 通过交换元素构建分界点 p
int p = partition(nums, lo, hi);
/************************/
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
从上面的代码和逻辑来看，快速排序的整个过程类似于二叉树的前序遍历。
归并排序的逻辑：若要对 nums[lo..hi] 进行排序，先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组排好序。
代码：
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
sort(nums, lo, mid);
sort(nums, mid + 1, hi);
/****** 后序遍历位置 ******/
// 合并两个排好序的子数组
merge(nums, lo, mid, hi);
/************************/
}
从上面的代码和逻辑来看，归并排序的整个过程类似二叉树的后序遍历。
关于树的相关算法
1、搞清楚当前root节点该做什么以及什么时候做
2、根据函数定义递归调用子节点，递归调用会让子节点做相同的事情。
算法实践
翻转二叉树 leetcode226
题目
输入一个二叉树根节点root，然后把整棵树镜像翻转，比如输入的二叉树如下：
4 / \ 2 7 / \ / \ 1 3 6 9
镜像翻转后，变成了：
4 / \ 7 2 / \ / \ 9 6 3 1
分析
我们只要把二叉树上的每一个节点的左右子节点进行交换，最后就是完全翻转之后的二叉树。
代码
public TreeNode invertTree(TreeNode root) {
if (root == null){
return null;
}
//root节点交换左右子节点（把交换的位置放在了前序遍历的位置）
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
//root节点的左右子节点递归地翻转它们各自的左右子节点
invertTree(root.left);
invertTree(root.right);
return root;
}
填充二叉树节点的右侧指针（leetcode 116）
题目
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例
输入：root = [1,2,3,4,5,6,7] 输出：[1,#,2,3,#,4,5,6,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
分析
从题目理解，可以套用上面的二叉树框架，因为都是用root节点的左节点指向右节点，按照这种思路可以写入如下的代码：
public Node connect1(Node root) {
if(root == null){
return null;
}
/*但是这里会导致，一个节点的右子节点和另一个节点的
左子节点相连的情况无法实现。
*/
root.left.next = root.right;
connect1(root.left);
connect1(root.right);
return root;
}
但是可以看到，这里只能将同一个节点下的左右子节点相连接（4,5），对于不同父节点的右节点和左节点（比如5,6）就无法实现。
对于这种，我们可以增加函数参数，一个节点无法实现，我们可以给函数参数为两个节点，就转化为了将每两个相邻的节点链接起来。
代码
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
class Solution {
public Node connect(Node root) {
if(root == null ){
return null;
}
connectTwoNode(root.left,root.right);
return root;
}
public void connectTwoNode(Node node1,Node 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);
}
}
构造最大的二叉树（leetcode 654）
题目
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
二叉树的根是数组 nums 中的最大元素。
左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树 。
示例
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
分析
从题目中可知，需要使用递归方法创建一棵最大二叉树。
1、根是数组的最大元素，那么需要从数组中找到最大元素，并把它放到根的位置。
2、对最大元素的左边和右边部分，分别再寻址最大元素，并且将最大元素放到相应的位置。
3、由于需要从数组中找到最大元素，因此需要在递归函数中添加两个参数，用来寻找最大元素以及确定数组的范围。
代码
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, 0, nums.length - 1);
}
public TreeNode build(int[] nums, int lo,int lw){
if(lo > lw){
return null;
}
int index = lo;
for(int i = lo; i <= lw; i++){
if(nums[i] > nums[index]){
index = i;
}
}
TreeNode root = new TreeNode(nums[index]);
root.left = build(nums, lo, index - 1);
root.right = build(nums, index + 1, lw);
return root;
}
}
如何判断使用前序还是中序还是后序遍历？
寻找重复的子树
题目
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例
1
/ \
2 3
/ / \
4 2 4
/
4
下面是两个重复的子树：
2
/
4
和
4
分析
第一步：思考对于某一个节点，它应该做什么？
对于节点2来说，需要知道以自己为根的子树是否重复，是够应该被加入到结果列表中。
第二步：要想知道以自己为根的子树是否重复，需要知道两点：
1、以自己为根的子树是什么样子的
对这个问题，需要使用后序遍历，因为得先知道自己的左右子树是什么样子，然后加上自己，就构成了一个完整的子树了。
2、以其他节点为根的子树是什么样子的
第三步：明确了需要使用后序遍历后，可以通过拼接字符串的方式将二叉树序列化，如下代码：
String traverse(TreeNode root){
//对空节点，可以用一个特殊字符表示
if(root == null){
return "#";
}
//将左右子树序列化成字符串
String left = traverse(root.left);
String right = traverse(root.right);
//后序遍历代码位置
//将左右子树加上自己，构成一个以自己为根的二叉树
String subTree = left + "," + right + "," + root.val;
return subTree;
}
从上面的代码可以知道，用拼接的方式将二叉树序列化了。
第四步：怎么知道以别的节点为根的子树是什么样子？
这里借助一个外部数据结构HashMap，来记录子树，同时记录子树出现的次数，这样就可以知道是否有重复了。
代码
class Solution {
HashMap<String, Integer> ans = new HashMap<>();
LinkedList<TreeNode> res = new LinkedList<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
traverse(root);
return res;
}
public String traverse(TreeNode root){
if(root == null){
return "#";
}
String left = traverse(root.left);
String right = traverse(root.right);
String subStr = left + "," + right + "," + root.val;
int feq = ans.getOrDefault(subStr,0);
if(feq == 1){
res.add(root);
}
ans.put(subStr, feq + 1);
return subStr;
}
}
这里用到了hashmap数据结构，HashMap是一个经常会用到的数据结构。
-
初学者必备：订单系统资料详解与实操教程12-25
-
内网穿透资料入门教程12-24
-
微服务资料入门指南12-24
-
微信支付系统资料入门教程12-24
-
微信支付资料详解：新手入门指南12-24
-
Hbase资料：新手入门教程12-24
-
Java部署资料12-24
-
Java订单系统资料：新手入门教程12-24
-
Java分布式资料入门教程12-24
-
Java监控系统资料详解与入门教程12-24
-
Java就业项目资料：新手入门必备教程12-24
-
Java全端资料入门教程12-24
-
Java日志系统资料详解：新手入门指南12-24
-
Java微服务系统资料：入门与初级应用指南12-24
-
Java小程序资料：入门教程与实战技巧12-24
