1、TreeNode的定义

以下题解中TreeNode的定义代码如下

1
2
3
4
5
6
7
8
9
10
11
12
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;
}
}

2、最大二叉树

2.1、题目介绍

这是 力扣第654题,题目具体要求如下

image-20210327160848365

2.2、解题思路

  • 重载所给的方法 buildTree,该方法有3个参数,分别为所给数组、搜寻左边界和搜寻右边界
  • 在重载的buildTree中,找到数组最大元素 maxValue ,并记录其下标为 index
  • maxValue 构造二叉树的根节点 root
  • 递归重载的 buildTree 方法,让右边界为 index - 1,得到根节点的左子节点
  • 递归重载的 buildTree方法,让左边界为 index + 1,得到根节点的右子节点

image-20210327162206973

2.3、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution01 {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return buildTree(nums,0,nums.length - 1);
}

private TreeNode buildTree(int[] nums, int left, int right) {
// 如果搜寻范围左边界严格大于右边界,此时退出递归
if(nums == null || nums.length == 0 || left > right) {
return null;
}
// 搜寻范围中的最大值
int maxValue = Integer.MIN_VALUE;
// 最大值下标
int index = 0;
// 找到范围中的数组最大值,并给上面的变量一一赋值
for (int i = left; i <= right; i++) {
if(nums[i] > maxValue) {
maxValue = nums[i];
index = i;
}
}
// 构造根节点
TreeNode root = new TreeNode(maxValue);
// 递归构造根节点的左子树,这里的右边界为 index - 1
root.left = buildTree(nums,left,index - 1);
// 递归构造根节点的右子树,这里的左边界为 index + 1
root.right = buildTree(nums, index + 1,right);
return root;
}
}

3、二叉树的镜像

3.1、题目介绍

这是剑指offer的第27道题,题目具体要求如下

image-20210327165240756

3.1、解题思路

这道题还算简单,使用一个临时节点,交换根节点的左右子树,然后向左右子树分别递归即可。

3.2、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution02 {
public TreeNode mirrorTree(TreeNode root) {
//递归退出条件,如果传入的root为空,那么直接直接返回null
if(root == null) {
return null;
}
//利用temp节点交换一个节点下的左右子树
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
//分别向左向右递归
mirrorTree(root.left);
mirrorTree(root.right);
//返回根节点
return root;
}
}

4、根据前序遍历结果和中序遍历结果还原二叉树

4.1、题目介绍

力扣的第105道题,题目介绍如下

image-20210327174038558

4.2、解题思路

在前序遍历中,顺序第一个结果便是树的根节点

在中序遍历中,根节点左边的节点元素(可能有0个或多个)是该节点的左子树,根节点右边的节点元素(可能有0个或多个)是该节点的右子树

  • 根据前序遍历结果,第一个元素为二叉树的根结点;
  • 观察中序遍历结果,根结点左侧的为左子树,若左子树根结点前(后)再无任何元素,则左(右)子树的左分支为空;根结点右侧的为右子树,若右子树根结点前(后)再无任何元素,则左(右)子树的左分支为空;
  • 上面的过程是递归的。先找到当前树的根结点,然后划分为左右子树,再进入左子树重复上面的过程,最后进入右子树重复上面的过程,最终还原一棵树。

例如:

已知前序遍历:ABDECFG

​ 中序遍历:DBEAFCG

  • 前序遍历中第一个元素为二叉树的根节点,所以A是二叉树根节点
  • 观察中需遍历结果,二叉树根节点左边的元素们构成该节点的左子树,故(DBE)构成A的左子树,(FCG)构成A的右子树
  • 观察前序遍历结果,发现前序遍历中A左子树节点的出现顺序为 (BDE),故B为A的左子节点,同理C为A的右子节点

image-20210327170248036

  • 在中序遍历中,DE分别出现在B的左右,故D为B的左子节点,E为B的右子节点,同理可得F为C的左子节点,G为C的右子节点,此时二叉树构造完毕

image-20210327170454885

  • 在前序遍历、中序遍历的结果数组中,我们可以作图如下

image-20210327170921862

  • 为数组中的元素标记下标,其中中序遍历中根节点的下标设置pIndex

image-20210327171544846

  • 这里我们需要求出前序遍历中左子数组的右边界和右子数组的左边界,由于前序遍历和中序遍历中左子数组的长度相等,我们可以列出一个式子,这里设左子树组的右边界为X

X - (preLeft + 1) = (pIndex - 1) - inLeft

可以解得 X 的值为 pIndex - inLeft + preLeft

image-20210327172129974

  • 先遍历中序遍历数组,找出最大值,以该值构造根节点
  • 递归左右子树,根据上面的规则构造出左子树和右子树

4.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;

return buildTree(preorder,0,preLen - 1,inorder,0,inLen - 1);
}

private TreeNode buildTree(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
//当传入的边界值构不成区间时,退出递归
if(preLeft > preRight || inLeft > inRight) {
return null;
}
//根节点为前序遍历中的左边界值
int rootValue = preorder[preLeft];
//构造根节点
TreeNode root = new TreeNode(rootValue);
//中序遍历中根节点的出现位置
int pIndex = 0;
//遍历中序数组,找到rootValue对应的下标,即根节点的位置
for (int i = inLeft; i <= inRight; i++) {
if(inorder[i] == rootValue) {
pIndex = i;
break;
}
}
//递归,构造左子树,这里需要传入前序遍历中左子数组的左右边界和中序遍历中左右数组的左右边界
root.left = buildTree(preorder,preLeft + 1,pIndex - inLeft + preLeft,inorder,inLeft,pIndex - 1);
root.right = buildTree(preorder,pIndex - inLeft + preLeft + 1,preRight,inorder,pIndex + 1,inRight);
return root;
}
}
  • 提交结果

image-20210327173642170

4.4、改进

使用一个 HashMap 保存中序数组中的数组值及下标,以数组值为键,下标为值,这样可以快速根据 preorder(preLeft) 获得中序结果中根节点的数组下标 pIndex

  • 改进后的代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;

Map<Integer, Integer> map = new HashMap<>();
//这里以数组值为键,数组下标为值,将中序遍历数组的数据放入map中
for (int i = 0; i < inLen; i++) {
map.put(inorder[i],i);
}
return buildTree(preorder,0,preLen - 1,map,0,inLen - 1);
}

private TreeNode buildTree(int[] preorder, int preLeft, int preRight, Map<Integer, Integer> inOrderMap, int inLeft, int inRight) {
if(preLeft > preRight || inLeft > inRight) {
return null;
}
int rootValue = preorder[preLeft];
TreeNode root = new TreeNode(rootValue);
int pIndex = inOrderMap.get(rootValue);
root.left = buildTree(preorder,preLeft + 1,pIndex - inLeft + preLeft,inOrderMap,inLeft,pIndex - 1);
root.right = buildTree(preorder,pIndex - inLeft + preLeft + 1,preRight,inOrderMap,pIndex + 1,inRight);
return root;
}
}
  • 执行结果

image-20210327173927388

5、根据后序遍历结果与中序遍历结果还原二叉树

5.1、题目介绍

力扣的第106道题,题目介绍如下

image-20210329113537190

5.2、解题思路

解题思路大体和105题一致,只不过在后序遍历中,根节点出现在后序遍历数组的最后,左右子数组的左右边界略有变化,我们可以通过一张图来说明

image-20210329114103215

从上图我们可以列出一条等式,即后序遍历结果中左子数组长度等于中需遍历结果中左子数组长度

X - postLeft = index - 1 - inLeft

X = postLeft + index - 1 - inLeft

5.3、代码实现

使用一个HashMap保存中序遍历数组中的数据,以空间换时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
private Map<Integer, Integer> inOrderData;
public TreeNode buildTree(int[] inorder, int[] postorder) {
// 初始化HashMap,用空间换时间的方式存储中序遍历数组中的数据
inOrderData = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inOrderData.put(inorder[i], i);
}
return buildTree(0,inorder.length - 1,postorder,0,postorder.length - 1);
}

private TreeNode buildTree(int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
//如果传入的边界无法构成区间,此时退出递归
if(inLeft > inRight || postLeft > postRight) {
return null;
}
// 后序遍历根节点在最后出现
int rootValue = postorder[postRight];
int index = inOrderData.get(rootValue);
TreeNode root = new TreeNode(rootValue);
root.left = buildTree(inLeft,index - 1,postorder,postLeft,postLeft + index - inLeft - 1);
root.right = buildTree(index + 1,inRight,postorder,postLeft + index - inLeft,postRight - 1);
return root;
}
}

5.4、结果

image-20210329114437615