首页 > 代码库 > 【LeetCode】Balanced Tree & Binary Search Tree

【LeetCode】Balanced Tree & Binary Search Tree

整合两道差不多的题目放上来,其中第一题是第二题的基础。

1.

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than one。

所谓高度平衡是指任意一个节点的两棵子树的深度相差不能超过1.

我的算法时间复杂度较高,是用了两次迭代,第一次是遍历每个节点,第二次则是在每个节点求其两个子树的深度时。这其中有很多重复计算,求深度时最好可以一次遍历就将所有子树深度存储下来,这样做比较好一些。

class Solution:
    # @param root, a tree node
    # @return a boolean
    def isBalanced(self, root):
        if root is None:
            return True
        elif abs(self.getDepth(root.left)-self.getDepth(root.right))>1:
            return False
        else:
            return self.isBalanced(root.left) & self.isBalanced(root.right)
    
    
    def getDepth(self, root):
        if root is None:
            return 0
        else:
            return max(self.getDepth(root.left),self.getDepth(root.right))+1

2.Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

BST(Binary Search Tree),二叉搜索树是对任意一个节点,其左子树值均比其小,右子树均比其大。

如图:

这样的结构有一个好处是很容易获得最大值(Maximum)、最小值(minimum)、某元素的前驱(Precursor)、某元素的后继(Successor)。

最大值:树的最右节点。

最小值:树的最左节点。

某元素前驱:左子树的最右。

某元素的后继:右子树的最左。

依然是通过迭代,每次找到数组的中间值作为节点,就可以保证左右子树的高度差不会超过1了。
class Solution:
    # @param num, a list of integers
    # @return a tree node
    def sortedArrayToBST(self, num):
        ll = len(num)
        root = None
        if ll != 0:
            root = TreeNode(num[ll/2])
            root.left = self.sortedArrayToBST(num[:ll/2])
            root.right= self.sortedArrayToBST(num[ll/2+1:])
        return root




【LeetCode】Balanced Tree & Binary Search Tree