以下5个习题是用dfs解决数组or链表和二叉树相互转换的问题，进行统一一起处理可以有效地增强学习，巩固记忆。
105. 从前序与中序遍历序列构造二叉树
题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
思路
首先如果想解决此题，首先知道前序和中序遍历的特征。前序遍历的特点是中左右，也就是说数组第一个元素也就是整个树根节点的值，而中序遍历的特点是左中右，也就是说左子树的节点都在根节点的左侧，右子树在根节点的右侧。
根据上面的特征，我们就可以根据前序+中序的遍历序列进行构建二叉树。
- 在前序遍历序列中找到树的根节点
- 在中序序列中找到这个根节点
- 然后递归构建子树
既然我们使用递归构建子树，就需要明确递归的几个条件
- 递归的结束条件
- 递归的顺序结构
首先是递归的结束条件，我们是根据树遍历结果来构建树，所以可以根据遍历的数组确定递归条件
if (instart == inEnd || preStart == preEnd) return;其次是递归的顺序结构，由于我们可以确定根节点的位置，然后才能找出其对应的左子树和右子树，所以这种情况就是先确定节点然后进行递归，类似于先序遍历。
ensure the root node;
recursion left;
recursion right;另外我们可以使用map将中序序列的遍历结果进行缓存，避免重复遍历，使用空间换时间。
代码实现
class Solution {
private Map<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
int index = 0;
for (int cur : inorder) {
map.put(cur, index++);
}
return build(preorder, inorder, 0, preorder.length, 0, inorder.length);
}
TreeNode build(int[] pre, int[] in, int pStart, int pEnd, int inStart, int inEnd) {
if (pStart == pEnd) return null;
int rootVal = pre[pStart];
int rootIndex = map.get(rootVal);
TreeNode root = new TreeNode(rootVal);
int leftNum = rootIndex - inStart;
root.left = build(pre, in, pStart + 1, pStart + 1 + leftNum, inStart, rootIndex);
root.right = build(pre, in, pStart + 1 + leftNum, pEnd, rootIndex + 1, inEnd);
return root;
}
}
106.从中序与后序遍历序列构造二叉树
题目描述
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
思路
这道题和上面的105题基本类似，没有太多区别。后序遍历的根节点是数组的最后一个元素。数组的边界是左开右闭。
代码
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
int index = 0;
for (int cur : inorder) {
map.put(cur, index++);
}
return build(inorder, postorder, 0, inorder.length, 0, postorder.length);
}
TreeNode build(int[] in, int[] post,int iStart, int iEnd, int pStart, int pEnd) {
if (iStart == iEnd || pStart == pEnd) return null;
int rootVal = post[pEnd - 1];
TreeNode root = new TreeNode(rootVal);
int rootIndex = map.get(rootVal);
int leftNum = rootIndex - iStart;
root.left = build(in, post, iStart, rootIndex, pStart, pStart + leftNum);
root.right = build(in, post, rootIndex + 1, iEnd, pStart + leftNum, pEnd - 1);
return root;
}
}
108. 将有序数组转换为二叉搜索树
题目描述
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5思路
首先根据题目描述，这道题提供的是一个升序的数组。我们都知道二叉搜索树的特征是中序遍历是有序的。所以，我们可以把这道题当做是将二叉搜索树中序遍历的结果进行还原。同时，题目给出一个条件就是高度差不超过1，也就是左右是平衡的。这样就可以使用二分搜索做了，mid索引其实就是对应根节点的位置，mid左边的就是根节点的左子树，反之就是右子树，依次递归就可以解决本题。
代码
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) return null;
return build(nums, 0, nums.length - 1);
}
TreeNode build(int[] nums, int left, int right) {
if (left > right) return null;
int mid = (right - left) / 2 + left;
TreeNode root = new TreeNode(nums[mid]);
root.left = build(nums, left, mid - 1);
root.right = build(nums, mid + 1, right);
return root;
}
}109.有序链表转换二叉搜索树
题目描述
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
思路
本题和108基本如出一辙，不同的地方在于本题是链表转换为树结构。链表计算中间节点的方式不像数组那么简单，链表是依靠快慢指针实现
slow = node;
fast = node;
while (fast.next != boarder && != fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;只要知道如何计算链表的中间节点，我们就可以继续使用二分构建树结构了。
代码
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
return build(head, null);
}
TreeNode build(ListNode left, ListNode right) {
if (left == right) return null;
ListNode mid = getMid(left, right);
TreeNode root = new TreeNode(mid.val);
root.left = build(left, mid);
root.right = build(mid.next, right);
return root;
}
ListNode getMid(ListNode left, ListNode right){
ListNode slow = left;
ListNode fast = left;
while (fast.next != right && fast.next.next != right) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}114.二叉树展开为链表
题目描述
给定一个二叉树，原地将它展开为一个单链表。
1
/ \
2 5
/ \ \
3 4 6
将其展开为：
1
\
2
\
3
\
4
\
5
\
6思路
展开的顺序仔细观察实际就是前序遍历的顺序，所以我们可以先将链表进行前序遍历，遍历的结果存储在List中。
展开的时候按照顺序进行构造关系，并且将左节点置为null就可以了。
当前节点的父亲节点是上一个节点的右子树
代码
class Solution {
List<TreeNode> list = new ArrayList<>();
public void flatten(TreeNode root) {
if (root == null) return ;
pre(root);
TreeNode pre = null;
TreeNode cur = null;
for (int i = 1; i < list.size(); i++) {
pre = list.get(i - 1);
cur = list.get(i);
pre.left = null;
pre.right = cur;
}
}
void pre(TreeNode root) {
if (root != null) {
list.add(root);
pre(root.left);
pre(root.right);
}
}
}
