二叉树是面试中常见的题目类型，这里，针对leetcode前200道题中的二叉树相关问题进行总结与思考，力求烂熟于心，能根据题目名回忆起题目的具体描述，进而用简洁的语言描述出算法的核心。具体的题目答案可打开leetcode查看历史提交记录。
二叉树的遍历是上一篇的内容，可先回顾；本篇主要整理二叉树的构造相关题目和思路。
二叉树的构造（binary-tree-traversal）
给定二叉树特定遍历下的结果，构造出原本的二叉树。
解题关键在于定位出根节点，划分出左右子树，然后 递归 构建左右子树
该题是leetcode105题，medium难度，一句话题干描述：从前序与中序遍历序列构造二叉树。
解决方案1(复杂度高)： 先序遍历的顺序是根节点，左子树，右子树。中序遍历的顺序是左子树，根节点，右子树。
所以我们只需要根据先序遍历得到根节点，然后在中序遍历中找到根节点的位置，它的左边就是左子树的节点，右边就是右子树的节点。生成左子树和右子树就可以递归的进行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length==0||inorder.length==0){
return null;
}
if(preorder.length!=inorder.length){
throw new RuntimeException("输入错误");
}
TreeNode root=new TreeNode(preorder[0]);
for(int i=0;i<preorder.length;i++){
if(preorder[0]==inorder[i]){
int[] pre_left=Arrays.copyOfRange(preorder,1,i+1);
int[] pre_right=Arrays.copyOfRange(preorder,i+1,preorder.length);
int[] in_left=Arrays.copyOfRange(inorder,0,i);
int[] in_right=Arrays.copyOfRange(inorder,i+1,inorder.length);
root.left=buildTree(pre_left,in_left);
root.right=buildTree(pre_right,in_right);
break;
}
}
return root;
}
|
二叉树相关的很多问题的解决思路都有分治法的思想在里面。我们复习一下分治法的思想：把原问题拆解成若干个与原问题结构相同但规模更小的子问题，待子问题解决以后，原问题就得以解决，“归并排序”和“快速排序”都是分治法思想的应用，其中“归并排序”先无脑地“分”，在“合”的时候就麻烦一些；“快速排序”开始在 partition 上花了很多时间，即在“分”上使了很多劲，然后就递归处理下去就好了，没有在“合”上再花时间。
解决方案2(优化版)： 以上的解法，存在两个问题：
1.在中序遍历中找到根节点的位置每次都得遍历中序遍历的数组去寻找，我们可以用一个HashMap把中序遍历数组的每个元素的值和下标存起来，这样寻找根节点的位置就可以直接得到；
2.每次递归都分割数组，占用空间大，其次只要传数组索引。
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
| class Solution {
private int[] preorder;
private Map<Integer,Integer> hash;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int prelength=preorder.length;
int inlength=inorder.length;
if(prelength!=inlength){
throw new RuntimeException("输入错误");
}
this.preorder=preorder;
this.hash=new HashMap<>();
for(int i=0;i<inlength;i++){
hash.put(inorder[i],i);
}
return buildTree(0,prelength-1,0,inlength-1);
}
private TreeNode buildTree(int preleft,int preright, int inleft,int inright) {
if(preleft>preright || inleft>inright){
return null;
}
TreeNode root=new TreeNode(preorder[preleft]);
int inindex=hash.get(preorder[preleft]);
root.left=buildTree(preleft+1,inindex-inleft+preleft,inleft,inindex-1);
root.right=buildTree(inindex-inleft+preleft+1,preright,inindex+1,inright);
return root;
}
}
|
该题是 leetcode106 题，medium 难度，一句话题干描述：从中序和后序遍历序列构造二叉树。
解决方案： 和上一题类似，中序遍历的顺序是左子树，根节点，右子树，后序遍历的顺序是左子树，右子树，根节点。所以我们只需要根据后序遍历得到根节点，然后在中序遍历中找到根节点的位置，它的左边就是左子树的节点，右边就是右子树的节点。生成左子树和右子树就可以递归的进行了。下面是更详细的图解。
直接套用上一题的解决方案2,使用哈希表和传数组索引的方法降低复杂度。
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
| class Solution {
private int[] postorder;
private Map<Integer,Integer> hash;
public TreeNode buildTree(int[] inorder, int[] postorder) {
int inLen=inorder.length;
int postLen=postorder.length;
if(inLen!=postLen){
throw new RuntimeException("输入错误");
}
this.hash=new HashMap<>();
this.postorder=postorder;
for(int i=0;i<inLen;i++){
hash.put(inorder[i],i);
}
return buildTree(0,inLen-1,0,postLen-1);
}
private TreeNode buildTree(int inLeft,int inRight,int postLeft,int postRight) {
if(inLeft>inRight || postLeft>postRight){
return null;
}
TreeNode root=new TreeNode(postorder[postRight]);
int inindex=hash.get(postorder[postRight]);
root.left=buildTree(inLeft,inindex-1,postLeft,inindex-inLeft+postLeft-1);
root.right=buildTree(inindex+1,inRight,inindex-inLeft+postLeft,postRight-1);
return root;
}
}
|
该题是 leetcode108 题，easy难度，一句话题干描述：根据升序数组，恢复一棵高度平衡的BST🌲。
解决方案：BST的中序遍历是升序的，因此本题等同于根据中序遍历的序列恢复二叉搜索树。因此我们可以以升序序列中的任一个元素作为根节点，以该元素左边的升序序列构建左子树，以该元素右边的升序序列构建右子树，这样得到的树就是一棵二叉搜索树啦～ 又因为本题要求高度平衡，因此我们需要选择升序序列的中间元素作为根节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return dfs(nums,0,nums.length-1);
}
private TreeNode dfs(int[] nums,int left,int right) {
if(left>right){
return null;
}
int mid=left+(right-left)/2;
TreeNode root=new TreeNode(nums[mid]);
root.left=dfs(nums,left,mid-1);
root.right=dfs(nums,mid+1,right);
return root;
}
}
|
该题是 leetcode109 题，medium 难度，一句话题干描述：根据升序数组，恢复一棵高度平衡的BST🌲。
解决方案：与上一题 leetcode108 题类似，唯一的不同在与数据结构，上一题是数组，这一题是链表，链表找中间根节点可以使用快慢指针法。
下面的代码与上图不同的地方是 构建左BST时没有断开链表，那处理的时候就是要改一下寻找中间节点的代码。while (fast != null && fast.next != null) ---》 while(fast!=tail && fast.next!=tail)
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
33
| class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head==null){
return null;
}
ListNode tail=head;
while(tail!=null){
tail=tail.next;
}
return dfs(head,tail);
}
private TreeNode dfs(ListNode head,ListNode tail) {
if(head==tail){
return null;
}
ListNode node=findMid(head,tail);
TreeNode root=new TreeNode(node.val);
root.left=dfs(head,node);
root.right=dfs(node.next,tail);
return root;
}
private ListNode findMid(ListNode head,ListNode tail) {
ListNode slow=head;
ListNode fast=head;
while(fast!=tail && fast.next!=tail){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
}
|
该题是 leetcode110 题，easy难度，一句话题干描述：给定一个二叉树，判断它是否是高度平衡的二叉树。
前两题要求构建的是平衡二叉树，我们的处理办法是从中间节点开始左右分别构建，这样的二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 ，也称作平衡二叉树。
解决方案(暴力法自顶向下)：构造一个获取当前节点最大深度的方法depth(root) ，通过比较此子树的左右子树的最大高度差abs(depth(root.left) - depth(root.right))，来判断此子树是否是二叉平衡树。若树的所有子树都平衡时，此树才平衡。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
return Math.abs(depth(root.left)-depth(root.right))<2 && isBalanced(root.left) && isBalanced(root.right);
}
public int depth(TreeNode root){
if(root==null){
return 0;
}else{
return Math.max(depth(root.left),depth(root.right))+1;
}
}
}
|
解决方案(优化法自底向上)：后序遍历，左右中，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。
NOTE:参数的话为传入的节点指针，就没有其他参数需要传递了，返回值要返回传入节点为根节点树的深度。
那么如何标记左右子树是否差值大于1呢。
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean isBalanced(TreeNode root) {
return dfs(root)!=-1;
}
private int dfs(TreeNode root){
if(root==null) return 0;
int left=dfs(root.left);
if(left==-1) return -1;
int right=dfs(root.right);
if(right==-1) return -1;
return Math.abs(left-right)<2?Math.max(left,right)+1:-1;
}
}
|
参考资料：leetcode题解，感谢这些大佬的配图以及易懂的语言！！
