【有书共读】《算法与数据结构题目最优解》（在线编程题总结3）
该书第三章——《二叉树问题》，核心有两大问题：DFS与BFS的理解与实现，以及二叉搜索树的实现。在做DFS的时候，主要思路是可以从上到下也可以从下到上，也就是分析每一个子树的根节点，然后分析该子树的内部子树或者外部子树的根节点，以此得出递归关系，也即是分治的思想。同时，对于每个节点的处理尝试利用前序、后序、中序遍历三种方法。 然而做BFS的时候，主要思路是从上到下，一层一层进行分析。参见：https://blog.csdn.net/yy254117440/article/details/53289598。
一、leetcode105&106（DFS与BFS）
1、利用前序和中序遍历构建二叉树。 构建一棵二叉树，如果是通过DFS的方式的话，那么分析每一个子树的根节点，将一个大子树分解成一个一个小的子树，分治下去，也就可以得出递归。
比如，有前序1，2，4，5，3，中序4，2，5，1，3。从前序中，我们可以得出一个条件：当前子树的根节点。 对于整个子树1，2，4，5，3，可以确定，1是该子树根节点，然后去中序中找1，1的左边是4，2，5，右边是3。因为中序的性质是在遍历完左子树后遍历当前根节点，所以说4，2，5就是1为父节点的一个新的子树。去前序中得到一个新的前序+中序数组对：2，4，5； 4，2，5，同理，2是该子树根节点，4是左子树，5在右子树， 以此类推分治递归下去。找到递归关系后，每一层根节点完成当前任务，然后将构建子树的任务交给左右子树递归过程即可。同时，我们思考的过程是从上到下，但程序递归运行的过程是从下到上，这点需要注意。可以写出代码：
TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length != inorder.length) return null;
if (preorder.length ==0) return null;
//完成当前任务，构建当前子树根节点。
TreeNode node = new TreeNode(preorder[0]);
if (preorder.length == 1) return node;
int root = preorder[0];
int leftCount=0;
//找到根节点位置
for (int i =0;i<inorder.length;i++) {
if (inorder[i] == root){
leftCount = i;
break;
}
}
//将新的构建任务递归交下去。
node.left = buildTree(Arrays.copyOfRange(preorder, 1, leftCount+1),Arrays.copyOfRange(inorder,0,leftCount));
node.right = buildTree(Arrays.copyOfRange(preorder, leftCount + 1, preorder.length ), Arrays.copyOfRange(inorder, leftCount + 1, inorder.length ));
return node;
}
2、利用后序和中序构建二叉树。 先找根节点！可以看到，当前整个子树根节点可以通过后续确定，然后利用中序确定左右子树来分治递归。思路类似。
二、leetcode108&109（二叉搜索树）
1、通过有序数组来构建一棵平衡二叉搜索树。
首先，对于一个有序数组，比如1，2，3，4，5，6。这里采用dfs解题。前面说过分析dfs时针对每一个子树的根节点，通过各个子树的根节点来寻找递归关系。
对于BST最上面的子树，根节点就是有序数组最中间的元素，令s = 0，e = 5，那么mid = s +(e-s)/2 = 2。也就是3是整个子树根节点，1，2是左子树内容，4，5，6是右子树内容。对于1，2有s = 0，e = 1，同理mid = 0，也就是1是该子树根节点，2是右子树内容。 以此类推很容易写出递归：
对于BST最上面的子树，根节点就是有序数组最中间的元素，令s = 0，e = 5，那么mid = s +(e-s)/2 = 2。也就是3是整个子树根节点，1，2是左子树内容，4，5，6是右子树内容。对于1，2有s = 0，e = 1，同理mid = 0，也就是1是该子树根节点，2是右子树内容。 以此类推很容易写出递归：
TreeNode dfs(int s,int e,int[] nums){
if(s > e) return null;
int mid = s + (e-s)/2;
TreeNode root = new TreeNode(nums[mid]);
root.left = dfs(s,mid-1,nums);
root.right = dfs(mid+1,e,nums);
return root;
}
建议画出递归栈，方便理解。在思考递归时，是从上到下思考，由整体到局部，但是程序运行时从下到上的，也就是dfs运行方式。是通过前序遍历的方式，在数组中依次拿出2，1，3，4，5，从下到上构建出BST，构建顺序是dfs的前序方式。
2、通过有序链表来构建一棵平衡二叉搜索树。
链表和数组不同了，数组可以随机访问，而链表只能顺序访问。所以，我们的思路应该是，依次将1，2，3，4，5填到BST的正确位置。利用类似1中的dfs，可以得到下图的递归栈，也就是说这5个符合条件的点就是BST中的点。我们从链表中依次拿出1，2，3，4，5，填入到这个树结构并构造BST。可以看到，对于1，应该填在0->1的位置，2填在1->1的位置，然后3填在0->4，4填在3->4，其实也就是以中序遍历的顺序填进去。这样一来，代码也就出来了：
TreeNode dfs(int s, int e) {
if (s > e) return null;
int mid = s + (e -s )/2;
TreeNode left = dfs(s, mid - 1);
TreeNode node = new TreeNode(head.val);
head = head.next;
TreeNode right = dfs(mid + 1, e);
node.left = left;
node.right = right;
return node;
}
可以看到，在构建树或者BST的过程中，找准根节点位置以及填放顺序，来相应处理即可。 
投递中兴等公司7个岗位 >