Balanced Binary Tree
QuestionGiven a binary tree,determine if it is height-balanced. For this problem,a height-balanced binary tree is defined as:
Example 1: Given the following tree? 3 / 9 20 / 15 7 Return true. Solution -- RecursionKey point of solution is that we need a helper function to get max height of left child tree and right child tree. In each level,get height is O(N) time complexity; and considering it‘s binary tree,level number is logN,so total time complexity is O(NlogN). 1 # Definition for a binary tree node. 2 # class TreeNode: 3 # def __init__(self,x): 4 # self.val = x 5 # self.left = None 6 # self.right = None 7 8 class Solution: 9 def isBalanced(self,root: TreeNode) -> bool: 10 def getHeight(node: TreeNode) -> int: 11 if not node: 12 return 0 13 return max(getHeight(node.left),getHeight(node.right)) + 1 14 15 if not root: 16 return True 17 left_val = getHeight(root.left) 18 right_val = getHeight(root.right) 19 if abs(left_val - right_val) > 1: 20 return False 21 return self.isBalanced(root.left) and self.isBalanced(root.right) Improved Solution?Evaluate child tree is balanced or not while calculation heights. Time complexity is O(N). 1 # Definition for a binary tree node. 2 # class TreeNode: 3 # def __init__(self,root: TreeNode) -> bool: 10 def getHeight(node: TreeNode) -> int: 11 if not node: 12 return 0 13 left = getHeight(node.left) 14 right = getHeight(node.right) 15 if left == -1 or right == -1: 16 return -1 17 if abs(left - right) > 1: 18 return -1 19 return max(left,right) + 1 20 21 if not root: 22 return True 23 return getHeight(root) != -1 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |