平衡二叉树

根据平衡二叉树的定义

平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1

class ListNode:
    def __init__(self, x)
        self.root = x
        self.Right = None
        self.Left = None


class Solution:
    def __init__(self):
        self.flag = True

    def IsBalanceTree(self, pRoot):
        self.GetMax(pRoot):
        return self.flag

    def GetMax(self, pRoot):
        if not pRoot:
            return 0
        left = 1 + self.GetMax(pRoot.left)
        Right = 1 + self.GetMax(pRoot.Right)
        if abs(left - Right) > 1:
            self.flag = False

        return left if left > Right else Right


class Solution:
    def GetDepth(self, pRoot):
        if pRoot == None:
            return 0
        return max(self.GetDepth(pRoot.left), self.GetDepth(pRoot.Right)) + 1

    def IsBalanceTree(self, pRoot):
        if pRoot == None:
            return True

        if abs(self.GetDepth(pRoot.left) - self.GetDepth(pRoot.Right)) > 1:
            return False
        return self.IsBalanceTree(pRoot.left) and self.GetDepth(pRoot.Right)

package main

type ListNode struct {
    Val     int
    Left    *ListNode
    Right   *ListNode
}

func isBalace(root *ListNode) bool {
    if root == nil {return true}

    var recur func(root *ListNode) (int bool)
    recur = func (root *ListNode) (int bool) {
        if root == nil {return 0, true}
        rightD, rightB := recur(root.Right)
        leftD, leftB := recur(root.Left)
        return max(rightD, leftD) + 1, abs(rightD-leftD) <= 1 && rightB && leftB 
    }
    _, res := recur(root)
    return res
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func max(a, b int) int {
    if a >= b {
        return a
    }
    return b
}