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