算法赏析

算法题不同思路赏析：
例题2，求根节点左右子树的高度差，然后再把根节点的左右子树按根节点的逻辑处理一遍。
例题3，这块递归的不是树，而是索引的位置
例题4，先中序遍历二叉树，然后使用单指针pre指向起始值，for循环遍历数组和单指针pre对比，pre跟随for循环i逐渐递增后移，将找到的值先存在x后存在y中，最后交换x y值。

def heightTree(root):
      if not root:
         return 0
      return  max(height(root.left),height(root.right))+1

例题2.  判断平衡二叉树
def isBalanced(self, root):
        def deep(tree):
            if not tree:
                return 0
            return max(deep(tree.left),deep(tree.right))+1
        if not root:
            return True
        return abs(deep(root.left)-deep(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

例题3. 有序数组构建二叉搜索树
    def sortedArrayToBST(self, nums):
        def helper(left, right):
            if left > right:
                return None
            mid = (left + right) // 2
            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root
        return helper(0, len(nums) - 1)

例题4. 还原有序二叉搜索树
    def recoverTree2(self, root):
        rs = []
        def bfs(root):
            if not root:
                return
            bfs(root.left)
            rs.append(root)
            bfs(root.right)
        bfs(root)

        x, y = None, None
        pre = rs[0]
        for i in range(1, len(rs)):
            if pre.val > rs[i].val:
                y = rs[i]
                if x == None:
                    x = pre
            pre = rs[i]

        if x and y:
            x.val, y.val = y.val, x.val