美文网首页
平衡二叉树

平衡二叉树

作者: 九日火 | 来源:发表于2021-01-10 14:02 被阅读0次

    根据平衡二叉树的定义

    平衡二叉树要求对于每一个节点来说,它的左右子树的高度之差不能超过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
    }
    

    相关文章

      网友评论

          本文标题:平衡二叉树

          本文链接:https://www.haomeiwen.com/subject/ijpcaktx.html