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题，题目具体要求如下
2.2、解题思路
- 重载所给的方法
buildTree，该方法有3个参数，分别为所给数组、搜寻左边界和搜寻右边界 - 在重载的
buildTree中，找到数组最大元素 maxValue ，并记录其下标为 index - 以
maxValue 构造二叉树的根节点 root - 递归重载的
buildTree 方法，让右边界为 index - 1，得到根节点的左子节点 - 递归重载的
buildTree方法，让左边界为 index + 1，得到根节点的右子节点
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);
root.left = buildTree(nums,left,index - 1);
root.right = buildTree(nums, index + 1,right);
return root;
}
}
|
3、二叉树的镜像
3.1、题目介绍
这是剑指offer的第27道题，题目具体要求如下
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) {
if(root == null) {
return null;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
mirrorTree(root.left);
mirrorTree(root.right);
return root;
}
}
|
4、根据前序遍历结果和中序遍历结果还原二叉树
4.1、题目介绍
力扣的第105道题，题目介绍如下
4.2、解题思路
在前序遍历中，顺序第一个结果便是树的根节点
在中序遍历中，根节点左边的节点元素（可能有0个或多个）是该节点的左子树，根节点右边的节点元素（可能有0个或多个）是该节点的右子树
- 根据前序遍历结果，第一个元素为二叉树的根结点；
- 观察中序遍历结果，根结点左侧的为左子树，若左子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；根结点右侧的为右子树，若右子树根结点前（后）再无任何元素，则左（右）子树的左分支为空；
- 上面的过程是递归的。先找到当前树的根结点，然后划分为左右子树，再进入左子树重复上面的过程，最后进入右子树重复上面的过程，最终还原一棵树。
例如：
已知前序遍历：ABDECFG
中序遍历：DBEAFCG
- 前序遍历中第一个元素为二叉树的根节点，所以
A是二叉树根节点 - 观察中需遍历结果，二叉树根节点左边的元素们构成该节点的左子树，故（DBE）构成A的左子树，（FCG）构成A的右子树
- 观察前序遍历结果，发现前序遍历中A左子树节点的出现顺序为 （BDE），故B为A的左子节点，同理C为A的右子节点
- 在中序遍历中，DE分别出现在B的左右，故D为B的左子节点，E为B的右子节点，同理可得F为C的左子节点，G为C的右子节点，此时二叉树构造完毕
- 在前序遍历、中序遍历的结果数组中，我们可以作图如下
- 为数组中的元素标记下标，其中中序遍历中根节点的下标设置
pIndex
- 这里我们需要求出前序遍历中左子数组的右边界和右子数组的左边界，由于前序遍历和中序遍历中左子数组的长度相等，我们可以列出一个式子，这里设左子树组的右边界为
X
X - (preLeft + 1) = (pIndex - 1) - inLeft
可以解得 X 的值为 pIndex - inLeft + preLeft
- 先遍历中序遍历数组，找出最大值，以该值构造根节点
- 递归左右子树，根据上面的规则构造出左子树和右子树
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;
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;
}
}
|
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<>();
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;
}
}
|
5、根据后序遍历结果与中序遍历结果还原二叉树
5.1、题目介绍
力扣的第106道题，题目介绍如下
5.2、解题思路
解题思路大体和105题一致，只不过在后序遍历中，根节点出现在后序遍历数组的最后，左右子数组的左右边界略有变化，我们可以通过一张图来说明
从上图我们可以列出一条等式，即后序遍历结果中左子数组长度等于中需遍历结果中左子数组长度
即 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) {
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、结果
