以下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); } }}