本文共 3980 字，大约阅读时间需要 13 分钟。

平衡二叉树的概念我想不用在多说了，每个计算机软件的学生都必须要掌握的知识，如果你还不记得这棵树的特征是什么，请充满愧疚的点开这里，没错，就是。

以下所说的四道题，统统都是采用递归的方式来构建树的，这是对于我来说最好理解的方法，但是递归毕竟效率不高，如果碰见严格的面试官他一定会你要优化的

---

先从最简单的一道题目入手

题目：Convert Sorted Array to Binary Search Tree

实现代码

# Definition for a  binary tree node# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    # @param alist, a list of integers    # @return a tree node    def sortedArrayToBST(self,alist):        if len(alist) == 0:            return None        if len(alist) == 1:            return TreeNode(alist[0])        left,right = 0,len(alist)-1        mid = (left + right ) // 2        root = TreeNode(alist[mid])        root.left = self.sortedArrayToBST(alist[:mid])        root.right = self.sortedArrayToBST(alist[mid+1:])        return root

---

在看看下这个题的变形

题目：Convert Sorted List to Binary Search Tree

基本思路

这个题不再是有序数组啦，而是有序链表，最简单最暴利的方法，当然是选择将有序链表转化为数组，简简单单加个循环就可以了。

代码

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = None# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def sortedListToBST(self, head):        """        :type head: ListNode        :rtype: TreeNode        """        # 需要额外空间的解法，将链表转化为数组        alist = []        p = head        while p:            alist.append(p.val)            p = p.next        return self.sortedArrayToBST(alist)    def sortedArrayToBST(self,alist):        if len(alist) == 0:            return None        if len(alist) == 1:            return TreeNode(alist[0])        left,right = 0,len(alist)-1        mid = (left + right ) // 2        root = TreeNode(alist[mid])        root.left = self.sortedArrayToBST(alist[:mid])        root.right = self.sortedArrayToBST(alist[mid+1:])        return root

---

接下来的两道题目就比较有意思了，给我们前序+中序 或者 后序+中序 来构建一个BST

这个就需要我们回忆以前做一种选择题的思路了，假设给你这样两个数组：

preorder = [3,9,20,15,7]inorder = [9,3,15,20,7]

你打算怎么构造一棵树呢？

前序遍历的特点是preorder的第一个节点一定是根结点，所以3是根结点，同时对应inorder中以3为中心，左边是左子树，右边是右子树，然后在对左右子树在继续这么做。

师傅以前教我，当你不知道怎么编写这个算法时，你就想象你平时是怎么做的，你就让代码怎么做，窃以为还是很有效的，这也是我师傅留给我的为数不多的经验之一。

题目：Construct Binary Tree from Preorder and Inorder Traversal

实现代码

这几段代码都惊人的相似，注意以下循环结束的条件即可

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def buildTree(self, preorder, inorder):        """        :type preorder: List[int]        :type inorder: List[int]        :rtype: TreeNode        """        # 使用递归        if len(preorder) == 0:            return None        if len(preorder) == 1:            return TreeNode(preorder[0])        root = TreeNode(preorder[0])        index = inorder.index(root.val)        root.left = self.buildTree(preorder[1:index+1],inorder[0:index])        root.right = self.buildTree(preorder[index+1:len(preorder)],inorder[index+1:len(inorder)])        return root

---

题目：Construct Binary Tree from Inorder and Postorder Traversal

代码

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def buildTree(self, inorder, postorder):        """        :type inorder: List[int]        :type postorder: List[int]        :rtype: TreeNode        """        if len(inorder) == 0:            return None        if len(inorder) == 1:            return TreeNode(inorder[0])        root = TreeNode(postorder[len(postorder) - 1])        index = inorder.index(postorder[len(postorder) - 1])        root.left = self.buildTree(inorder[ 0 : index ], postorder[ 0 : index ])        root.right = self.buildTree(inorder[ index + 1 : len(inorder) ], postorder[ index : len(postorder) - 1 ])        return root

---

树这块的代码感觉是比较难得，但是我们可以先从递归写法开始练习，慢慢慢慢的过度到非递归，这是个过程，不要心急。

同事小姐姐告诉我他写了leetcode * 3 遍了，身边优秀的人有很多，继续学习，永远在路上！